Complexity Results for Nonmonotonic Logics
Copyright policy )Complexity Results for Nonmonotonic Logics
The paper provides complexity results for three problems of several nonmonotonic logics. Testing of existence of a fixed point and deciding whether a formula belongs to at least one fixed point are \(\Sigma^ P_ 2\)-complete. Deciding whether a formula belongs to all fixed points is \(\Pi^ P_ 2\)-complete. Reasoning in nonmonotonic logics turns out to be harder than reasoning in classical propositional calculus.
- University of Oxford United Kingdom
- TU Wien Austria
Complexity of computation (including implicit computational complexity), Logic in artificial intelligence, fixed point, nonmonotonic logics, Analysis of algorithms and problem complexity, Other nonclassical logic
Complexity of computation (including implicit computational complexity), Logic in artificial intelligence, fixed point, nonmonotonic logics, Analysis of algorithms and problem complexity, Other nonclassical logic
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).207 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 1% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!