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)

Full work available at URL https://doi.org/10.1137/S0097539704446311

zbMATH Keywords

abductionBoolean constraintscomplexitypropositional logic

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) 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

(25)

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

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)