Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete (Q2367539): Difference between revisions

For non-monotonic logics (logic programming, default reasoning, etc.), several versions of Closed World Assumption are known. All of them express the idea that, crudely speaking, all possible knowledge about the domain area is already included in the knowledge base, so if some statement is not deducible from the knowledge base, then it must be false. The authors analyze the complexity of the following deduction problem: given a (finite) propositional theory with an appropriate version of CWA, and a query \(Q\), to check whether \(T\) (together with this version of CWA) implies \(Q\). For all known versions of CWA, except the so-called ``simple'' CWA, this deduction problem is proven to be \(\Pi^ P_ 2\)-hard (i.e., at least as hard as the problem of checking whether a formula of the type \(\forall \vec x\;\exists \vec y\;B( \vec x,\vec y,\vec u)\) is satisfiable, where \(\vec x= (x_ 1,\dots,x_ n)\), \(\vec y=(y_ 1,\dots,y_ m)\), and \(\vec u=(u_ 1,\dots,u_ l)\) are sets of Boolean variables). For simple CWA, the deduction problem belongs to the class \(\Delta^ P_ 2\), and, most probably, is even easier, but it is still harder than the deduction problem in normal propositional logic (without CWA).