A Complete Classification of the Complexity of Propositional Abduction
From MaRDI portal
Publication:5470752
DOI10.1137/S0097539704446311zbMath1111.68045MaRDI QIDQ5470752
Bruno Zanuttini, Nadia Creignou
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
What makes propositional abduction tractable ⋮ On the Boolean connectivity problem for Horn relations ⋮ Complexity Classifications for Logic-Based Argumentation ⋮ Unnamed Item ⋮ On the complexity of second-best abductive explanations ⋮ Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ Unnamed Item ⋮ A complexity theory for hard enumeration problems ⋮ Counting complexity of propositional abduction ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?