On the Complexity of Fragments of Nonmonotonic Logics (PDF)

Nonmonotonic reasoning is one of the most important tasks in the area of knowledge representation and reasoning. Several logics have been developed to formalize nonmonotonic reasoning. In this thesis we consider three well-known logics that facilitate nonmonotonic reasoning by different means: default logic, autoepistemic logic and circumscription. We study the computational complexity of consistency, reasoning and counting problems for fragments of these logics obtained by restricting the available Boolean connectives, as well as the possibility to translate between these fragments. For this we generalize the logics to allow for arbitrary connectives rather than the Boolean standard base and study the complexity of the problems and possibility of translations for all finite sets of allowed Boolean connectives.
Our results show that in all cases the complexity of the problems does not depend on the particular set B of available connectives but on the set of functions expressible by projections and arbitrary compositions from B. We obtain polytomous complexity classifications (that is, into a finite number of complexity degrees) for all decision problems studied herein ranging from completeness for classes in the second level of the polynomial hierarchy down to membership in AC0. Furthermore, the counting problems are with one interesting exception shown to be trichotomous with complexity degrees spanning the first three levels of the counting hierarchy. To the best of our knowledge, the counting complexity of default logic is addressed here for the first time.
Finally, we consider translations between fragments of these logics that leave the set of propositional consequences of the input invariant. We show which fragments of default logic, autoepistemic logic and circumscription can, under the chosen notion of translations, be embedded into fragments of the other two logics. We complete this picture by showing that in almost all cases in which no translation is given, no translation preserving the set of propositional consequences may exist unless the polynomial hierarchy collapses.