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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
scientific article

    Statements

    Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete (English)
    0 references
    0 references
    0 references
    19 September 1993
    0 references
    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).
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    circumsription
    0 references
    \(\Pi^ P_ 2\)-complete
    0 references
    closed world assumption
    0 references
    non-monotonic logics
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references