On the counting complexity of propositional circumscription

DOI10.1016/j.ipl.2007.11.006zbMath1186.68448OpenAlexW2019722250MaRDI QIDQ963360

Miki Hermann, Arnaud Durand

Publication date: 19 April 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.11.006

zbMATH Keywords

computational complexitycounting complexityHornand affine formulasbijunctivedual HornHypergraph transversalpropositional circumscription

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

The complexity of counting locally maximal satisfying assignments of Boolean CSPs ⋮ Counting minimal transversals of \(\beta\)-acyclic hypergraphs ⋮ Counting Minimal Dominating Sets ⋮ Counting Constraint Satisfaction Problems.

Cites Work

• Unnamed Item
• Unnamed Item
• Generating all maximal models of a Boolean expression
• The complexity of computing the permanent
• Circumscription - a form of non-monotonic reasoning
• The complexity of model checking for circumscriptive formulae
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• The complexity of minimal satisfiability problems
• Subtractive reductions and complete problems for counting complexity classes
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• The Complexity of Enumeration and Reliability Problems
• Minimal vectors in linear codes
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• The complexity of satisfiability problems

This page was built for publication: On the counting complexity of propositional circumscription