PROPOSITIONAL CIRCUMSCRIPTION AND EXTENDED CLOSED-WORLD REASONING AREPI-P2-COMPLETE

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.