T. Eiter et G. Gottlob, PROPOSITIONAL CIRCUMSCRIPTION AND EXTENDED CLOSED-WORLD REASONING AREPI-P2-COMPLETE, Theoretical computer science, 114(2), 1993, pp. 231-245
Circumscription and the closed-world assumption with its variants are
well-known nonmonotonic techniques for reasoning with incomplete knowl
edge. Their complexity in the propositional case has been studied in d
etail for fragments of propositional logic. One open problem is whethe
r the deduction problem for arbitrary propositional theories under the
extended closed-world assumption or under circumscription is PI2P-com
plete, i.e., complete for a class of the second level of the polynomia
l hierarchy. We answer this question by proving these problems PI2P-co
mplete, and we show how this result applies to other variants of close
d-world reasoning.