The Complexity of Propositional Default Logics

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Volume

Representation and Reasoning

Representation and Reasoning: Tractability

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 X; complete, even for semi-normal theories, and that the extension membership and entailment problems are X; complete and IIp2; 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.