Propositional circumscription and extended closed-world reasoning are ΠP2-complete

1993/06/01 by Thomas Eiter, Georg Gottlob · 6 citations
Computer Science · #Advanced Algebra and Logic #Logic, Reasoning, and Knowledge #Logic, programming, and type systems

paper · pdf · doi:10.1016/0304-3975(93)90073-3

crossref issued 1993/06/01 · crossref published 1993/06/01 · crossref published-print 1993/06/01 · openalex publication_date 1993/06/01 · crossref created 2002/07/26 · crossref deposited 2019/04/13 · openalex created_date 2025/10/10 · crossref indexed 2026/07/14 · openalex updated_date 2026/08/02

Cited by

• The complexity of propositional closed world reasoning and circumscription
• Complexity and expressive power of logic programming
• Logic programming and knowledge representation
• Technical Note: Exploring Σ^P₂ / Π^P₂-hardness for Argumentation Problems with fixed distance to tractable classes
• The Complexity of Computing Minimal Unidirectional Covering Sets
• Closed-world assumption [wikipedia]