The complexity of model checking for propositional default logics

We analyze the complexity of deciding whether a propositional interpretation is a model of a default theory for some of the variants of default logic presented in the literature: Reiter's, Justified, constrained, rational, and cumulative. We prove that all the analyzed variants are Sigma(p)(2)-complete in the general case, and remains so even if all defaults are prerequisite-free and seminormal. Cumulative default logic is also Sigma(p)(2)-complete even if all defaults are normal and prerequisite-free. The other semantics are Delta(p)(2)[log n]-complete and coNP-complete if all defaults are normal and prerequisites are allowed or not, respectively. (c) 2005 Elsevier B.V. All rights reserved.