Approximating cost-based abduction is NP-hard

DOI10.1016/j.artint.2004.06.001zbMath1086.68132OpenAlexW2012523515MaRDI QIDQ814635

Ashraf M. Abdelbar

Publication date: 7 February 2006

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2004.06.001

zbMATH Keywords

ComplexityUncertaintyBelief revisionDiagnosisExplanation

Mathematics Subject Classification ID

Reasoning under uncertainty in the context of artificial intelligence (68T37) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Solving abduction by computing joint explanations. Logic programming formalization, applications to P2P data integration, and complexity results ⋮ Recurrent neural networks with backtrack-points and negative reinforcement applied to cost-based abduction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear constraint satisfaction approach to cost-based abduction
• Cost-based abduction and MAP explanation
• Networked bubble propagation: a polynomial-time hypothetical reasoning method for computing near-optimal solutions
• Polynomial solvability of cost-based abduction
• The complexity of logic-based abduction
• Efficient probabilistically checkable proofs and applications to approximations
• An algorithm for finding MAPs for belief networks through cost-based abduction

This page was built for publication: Approximating cost-based abduction is NP-hard