Approximating cost-based abduction is NP-hard

DOI10.1016/J.ARTINT.2004.06.001MaRDI QIDQ814635zbMATH OpenOpenAlexFDO

Authors 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

Belief revisionComplexityDiagnosisExplanationUncertainty

Mathematics Subject Classification ID

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

Recommendations

• An efficient LP-based admissible heuristic for cost-based abduction
• The computational complexity of abduction
• Polynomial solvability of cost-based abduction
• Finding MAPs for belief networks is NP-hard
• Approximating MAPs for belief networks is NP-hard and other theorems

Cites work

• A linear constraint satisfaction approach to cost-based abduction
• An algorithm for finding MAPs for belief networks through cost-based abduction
• Cost-based abduction and MAP explanation
• Efficient probabilistically checkable proofs and applications to approximations
• scientific article; zbMATH DE number 19872 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 1929157 (Why is no real title available?)
• 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

Cited in

(5)

• Cost-based abduction and MAP explanation
• 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
• An efficient LP-based admissible heuristic for cost-based abduction
• 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

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