Complexity Results for Nonmonotonic Logics

Abstract

The complexity of different reasoning tasks in nonmonotonic propositional logics is investigated. The systems of logic we considered are Reiter's default logic, McDermott's and Doyle's nonmonotonic logic, Moore's autoepistemic logic, and Marek's and Truszczyński's nonmonotonic logic N. All these logics have in common that the semantics of an initially given set of premises is explained through a corresponding set of fixed points (also called extensions or expansions). Given a set of premises, the main reasoning tasks in these logics are: (1) testing for existence of a fixed-point; (2) deciding whether a given formula belongs to at least one fixed-point (brave reasoning); and (3) deciding whether a given formula belongs to all fixed-points (cautious reasoning). We show that for all mentioned logics, the first and the second problem are complete for the class $∑2P$ of the polynomial hierarchy, while the third problem is complete for the dual class $∏2P$. Thus, unless the polynomial hierarchy collapses, reasoning in nonmonotonic logics is strictly harder than reasoning in classical propositional calculus.