Propositional circumscription and extended closed-world reasoning are _ 2^ P-complete
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).
- The complexity of propositional closed world reasoning and circumscription
- On compact representations of propositional circumscription
- On compact representations of propositional circumscription
- A dichotomy in the complexity of propositional circumscription
- Generalized closed world assumption is \(\Pi ^ 0_ 2\)-complete
- Logic for Programming, Artificial Intelligence, and Reasoning
- On a new proof of completeness of p.i. propositional calculus
- scientific article; zbMATH DE number 1962835
- The Completeness of Propositional Resolution: A Simple and Constructive Proof
- Some Completeness Results for Propositional Conditional Logics
- \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
- Bounded Query Classes
- Circumscription - a form of non-monotonic reasoning
- Decidability and definability with circumscription
- Deduction in non-Horn databases
- Generalized closed world assumption is \(\Pi ^ 0_ 2\)-complete
- scientific article; zbMATH DE number 3755910 (Why is no real title available?)
- scientific article; zbMATH DE number 8776 (Why is no real title available?)
- scientific article; zbMATH DE number 3560737 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1303203 (Why is no real title available?)
- scientific article; zbMATH DE number 1142309 (Why is no real title available?)
- scientific article; zbMATH DE number 1980915 (Why is no real title available?)
- Inferring negative information from disjunctive databases
- More complicated questions about maxima and minima, and some closures of NP
- Negation as failure: careful closure procedure
- NP is as easy as detecting unique solutions
- On computing Boolean connectives of characteristic functions
- On the relationship between circumscription and negation as failure
- On the unique satisfiability problem
- Polynomial terse sets
- Some computational aspects of circumscription
- The complexity of facets (and some facets of complexity)
- The complexity of optimization problems
- The complexity of propositional closed world reasoning and circumscription
- The NP-completeness column: An ongoing guide
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- The Semantics of Predicate Logic as a Programming Language
- Weak generalized closed world assumption
- The computational complexity of ideal semantics
- Closed-world databases and circumscription
- Reasoning with minimal models: efficient algorithms and applications
- Circumscribing DATALOG: expressive power and complexity
- On the complexity of propositional knowledge base revision, updates, and counterfactuals
- The complexity of model checking for circumscriptive formulae
- The complexity of propositional closed world reasoning and circumscription
- Cumulative default logic: Finite characterization, algorithms, and complexity
- On compact representations of propositional circumscription
- Reducing belief revision to circumscription (and vice versa)
- Compiling specificity into approaches to nonmonotonic reasoning
- Semantical and computational aspects of Horn approximations
- The complexity of belief update
- Default reasoning from conditional knowledge bases: Complexity and tractable cases
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Minimal sets on propositional formulae. Problems and reductions
- On the computational complexity of assumption-based argumentation for default reasoning.
- On the complexity of data disjunctions.
- Preprocessing of intractable problems
- A decision method for nonmonotonic reasoning based on autoepistemic reasoning
- PP is closed under truth-table reductions
- ECWA made easy
- On the computational cost of disjunctive logic programming: Propositional case
- Complexity of computing with extended propositional logic programs
- On the decidability and complexity of reasoning about only knowing
- Choice logics and their computational properties
- Graph-based construction of minimal models
- Bounded treewidth as a key to tractability of knowledge representation and reasoning
- Redundancy in logic. III: Non-monotonic reasoning
- An incremental algorithm for generating all minimal models
- Knowledge compilation for closed world reasoning and circumscription
- Abstraction-based algorithm for 2QBF
- Seminormalizing a default theory
- scientific article; zbMATH DE number 589696 (Why is no real title available?)
- scientific article; zbMATH DE number 1962835 (Why is no real title available?)
- On compact representations of propositional circumscription
- A tableau calculus for minimal model reasoning
- On the tractability of minimal model computation for some CNF theories
- Counterexample guided abstraction refinement algorithm for propositional circumscription
- On the parameterized complexity of non-monotonic logics
- Theorem proving techniques for view deletion in databases
- CWA formalizations in multi-valued logics
- Closed world assumption for disjunctive reasoning
- Prolegomena to logic programming for non-monotonic reasoning
- The complexity of circumscriptive inference in Post's lattice
- Trichotomies in the complexity of minimal inference
- Complexity of counting the optimal solutions
- Reasoning under minimal upper bounds in propositional logic
- Generalized closed world assumption is \(\Pi ^ 0_ 2\)-complete
- Closed world assumptions having precedence in predicates
This page was built for publication: Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2367539)
