Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
type: Item
instance of: scholarly article
title: Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
zbMATH Open document ID: 0786.68085
DOI: 10.1016/0304-3975(93)90073-3
author: Thomas Eiter
author: Georg Gottlob
published in: Theoretical Computer Science
publication date: 1993-09-19T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 68T27
Mathematics Subject Classification ID: 68T15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03B60
zbMATH DE Number: 269346
zbMATH Keywords: circumsription
zbMATH Keywords: \(\Pi^ P_ 2\)-complete
zbMATH Keywords: closed world assumption
zbMATH Keywords: non-monotonic logics
Wikidata QID: Q56815066
reviewed by: Vladik Kreinovich
MaRDI profile type: Publication
full work available at URL: 0304-3975(93)90073-3
OpenAlex ID: W2083568285
cites work: Polynomial terse sets
cites work: Q4428289
cites work: On the unique satisfiability problem
cites work: The complexity of propositional closed world reasoning and circumscription
cites work: On computing Boolean connectives of characteristic functions
cites work: Q3971264
cites work: Generalized closed world assumption is \(\Pi ^ 0_ 2\)-complete
cites work: Q4198056
cites work: Q4249726
cites work: Negation as failure: careful closure procedure
cites work: On the relationship between circumscription and negation as failure
cites work: The NP-completeness column: An ongoing guide
cites work: Q4385525
cites work: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
cites work: \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
cites work: Some computational aspects of circumscription
cites work: The complexity of optimization problems
cites work: Circumscription - a form of non-monotonic reasoning
cites work: Q3939270
cites work: The complexity of facets (and some facets of complexity)
cites work: Weak generalized closed world assumption
cites work: Inferring negative information from disjunctive databases
cites work: Decidability and definability with circumscription
cites work: Q4131648
cites work: NP is as easy as detecting unique solutions
cites work: The Semantics of Predicate Logic as a Programming Language
cites work: More complicated questions about maxima and minima, and some closures of NP
cites work: Bounded Query Classes
cites work: Deduction in non-Horn databases
Recommended article: The complexity of propositional closed world reasoning and circumscription
Recommended article: On compact representations of propositional circumscription
Recommended article: A dichotomy in the complexity of propositional circumscription
Recommended article: Generalized closed world assumption is \(\Pi ^ 0_ 2\)-complete
Recommended article: Logic for Programming, Artificial Intelligence, and Reasoning
Recommended article: Q5426855
Recommended article: Q4418672
Recommended article: The Completeness of Propositional Resolution: A Simple and Constructive Proof
Recommended article: Some Completeness Results for Propositional Conditional Logics
description: scientific article