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 II; 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.
We present a new context-based approach to default logic, called contextual default logic. The approach"extends the notion of a default rule and supplies each extension with a context. Contextual default logic allows for embedding all existing variants of default logic along with more traditional approaches like the closed world assumption. A key advantage of contextual default logic is that it provides a syntactical instrument for comparing existing default logics in a unified setting. In particular, it reveals that existing default logics mainly differ in the way they deal with an explicit or implicit underlying context.