A Complete Classification of the Complexity of Propositional Abduction

DOI10.1137/S0097539704446311MaRDI QIDQ5470752zbMATH OpenFDO

Authors Nadia Creignou, Bruno Zanuttini

Publication date 1 June 2006

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

complexityabductionpropositional logicBoolean constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in artificial intelligence (68T27)

Recommendations

• Complexity classifications for propositional abduction in Post's framework
• What makes propositional abduction tractable
• scientific article; zbMATH DE number 512816
• Computer Science Logic
• The complexity of logic-based abduction

Cited in

(22)

• Computer Science Logic
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• scientific article; zbMATH DE number 6970794 (Why is no real title available?)
• Counting complexity of propositional abduction
• On computing all abductive explanations from a propositional Horn theory
• On the Boolean connectivity problem for Horn relations
• Multilevel descriptions of classes decreasing the number of steps in solving pattern recognition problems described by propositional formulas
• Complexity results for abductive logic programming
• Complexity classifications for propositional abduction in Post's framework
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• Completeness for cut-based abduction
• Complexity of Possible and Necessary Existence Problems in Abstract Argumentation
• On the complexity of second-best abductive explanations
• Compilability of propositional abduction
• scientific article; zbMATH DE number 140373 (Why is no real title available?)
• Propositional truth maintenance systems: Classification and complexity analysis
• What makes propositional abduction tractable
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• scientific article; zbMATH DE number 7536562 (Why is no real title available?)
• Complexity Classifications for Logic-Based Argumentation
• Parameterized complexity of abduction in Schaefer's framework
• scientific article; zbMATH DE number 2000816 (Why is no real title available?)

This page was built for publication: A Complete Classification of the Complexity of Propositional Abduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470752)