Counting complexity of propositional abduction

DOI10.1016/j.jcss.2009.12.001zbMath1197.68072OpenAlexW2032312337MaRDI QIDQ988576

Miki Hermann, Reinhard Pichler

Publication date: 18 August 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2009.12.001

zbMATH Keywords

computational complexitycounting complexityHorndual Hornbijunctive formulasdefinite Hornpropositional abduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27)

Related Items

What makes propositional abduction tractable ⋮ On the complexity of second-best abductive explanations ⋮ Unnamed Item ⋮ On the complexity of inconsistency measurement

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Complexity of counting the optimal solutions
• The complexity of optimization problems
• The computational complexity of abduction
• Generalizations of Opt P to the polynomial hierarchy
• Probabilistic Horn abduction and Bayesian networks
• On some tractable classes in deduction and abduction
• What makes propositional abduction tractable
• Subtractive reductions and complete problems for counting complexity classes
• Counting Complexity of Minimal Cardinality and Minimal Weight Abduction
• The Complexity of Enumeration and Reliability Problems
• The complexity of logic-based abduction
• Computer Science Logic
• The complexity of satisfiability problems
• A Complete Classification of the Complexity of Propositional Abduction
• Logic Programming and Nonmonotonic Reasoning