Propositional circumscription and extended closed-world reasoning are ΠP2-complete

AbstractCircumscription and the closed-world assumption with its variants are well-known nonmonotonic techniques for reasoning with incomplete knowledge. Their complexity in the propositional case has been studied in detail for fragments of propositional logic. One open problem is whether the deduction problem for arbitrary propositional theories under the extended closed-world assumption or under circumscription is ΠP2-complete, i.e., complete for a class of the second level of the polynomial hierarchy. We answer this question by proving these problems ΠP2-complete, and we show how this result applies to other variants of closed-world reasoning