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

DOI10.1016/0304-3975(93)90073-3zbMath0786.68085OpenAlexW2083568285WikidataQ56815066 ScholiaQ56815066MaRDI QIDQ2367539

Georg Gottlob, Thomas Eiter

Publication date: 19 September 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90073-3

zbMATH Keywords

closed world assumptionnon-monotonic logicscircumsription\(\Pi^ P_ 2\)-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other nonclassical logic (03B60) Logic in artificial intelligence (68T27)

Related Items

The complexity of propositional closed world reasoning and circumscription, Cumulative default logic: Finite characterization, algorithms, and complexity, Complexity of counting the optimal solutions, A decision method for nonmonotonic reasoning based on autoepistemic reasoning, Redundancy in logic. III: Non-monotonic reasoning, Reasoning under minimal upper bounds in propositional logic, The complexity of computing minimal unidirectional covering sets, Reasoning with minimal models: efficient algorithms and applications, Circumscribing DATALOG: expressive power and complexity, On the computational cost of disjunctive logic programming: Propositional case, Complexity of computing with extended propositional logic programs, Minimal sets on propositional formulae. Problems and reductions, On compact representations of propositional circumscription, Reducing belief revision to circumscription (and vice versa), Compiling specificity into approaches to nonmonotonic reasoning, An incremental algorithm for generating all minimal models, On the tractability of minimal model computation for some CNF theories, On the decidability and complexity of reasoning about only knowing, On the parameterized complexity of non-monotonic logics, Abstraction-Based Algorithm for 2QBF, A tableau calculus for minimal model reasoning, On the complexity of propositional knowledge base revision, updates, and counterfactuals, Theorem proving techniques for view deletion in databases, The complexity of circumscriptive inference in Post's lattice, Trichotomies in the complexity of minimal inference, The complexity of model checking for circumscriptive formulae, Bounded treewidth as a key to tractability of knowledge representation and reasoning, Closed world assumption for disjunctive reasoning, Seminormalizing a default theory, Semantical and computational aspects of Horn approximations, The complexity of belief update, Choice logics and their computational properties, The computational complexity of ideal semantics, Graph-based construction of minimal models, Default reasoning from conditional knowledge bases: Complexity and tractable cases, On the computational complexity of assumption-based argumentation for default reasoning., On the complexity of data disjunctions., Preprocessing of intractable problems, Fixed-parameter complexity in AI and nonmonotonic reasoning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decidability and definability with circumscription
• \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
• Generalized closed world assumption is \(\Pi ^ 0_ 2\)-complete
• The complexity of facets (and some facets of complexity)
• NP is as easy as detecting unique solutions
• Negation as failure: careful closure procedure
• Polynomial terse sets
• The complexity of optimization problems
• More complicated questions about maxima and minima, and some closures of NP
• Inferring negative information from disjunctive databases
• On the relationship between circumscription and negation as failure
• Circumscription - a form of non-monotonic reasoning
• The complexity of propositional closed world reasoning and circumscription
• Deduction in non-Horn databases
• Weak generalized closed world assumption
• On the unique satisfiability problem
• Some computational aspects of circumscription
• Bounded Query Classes
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The Semantics of Predicate Logic as a Programming Language
• On computing Boolean connectives of characteristic functions
• The NP-completeness column: An ongoing guide