A Complete Classification of the Complexity of Propositional Abduction

DOI10.1137/S0097539704446311zbMATH Open1111.68045MaRDI QIDQ5470752FDOQ5470752

Authors: Nadia Creignou, Bruno Zanuttini 

Publication date: 1 June 2006

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

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

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)

Cited In (23)

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

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)