The Complexity of Propositional Default Logics

Abstract

We characterize the complexity of several typical problems in propositional default logics. In particular, we examine the complexity of extension membership, extension existence, and extension entailment problems. We show that the extension existence problem is Σ2p complete, even for semi-normal theories, and that the extension membership and entailment problems are Σ2p complete and Π2p complete respectively, even when restricted to normal default theories. These results contribute to our understanding of the computational relationship between propositional default logics and other formalisms for nonmonotonic reasoning, e.g., autoepistemic logic and McDermott and Doyle's NML, as well as their relationship to problems outside the realm of nonmonotonic reasoning.