Approximating cost-based abduction is NP-hard
From MaRDI portal
Publication:814635
DOI10.1016/J.ARTINT.2004.06.001zbMATH Open1086.68132OpenAlexW2012523515MaRDI QIDQ814635FDOQ814635
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
Recommendations
Reasoning under uncertainty in the context of artificial intelligence (68T37) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient probabilistically checkable proofs and applications to approximations
- Cost-based abduction and MAP explanation
- The complexity of logic-based abduction
- Title not available (Why is that?)
- A linear constraint satisfaction approach to cost-based abduction
- Networked bubble propagation: a polynomial-time hypothetical reasoning method for computing near-optimal solutions
- Polynomial solvability of cost-based abduction
- Title not available (Why is that?)
- An algorithm for finding MAPs for belief networks through cost-based abduction
Cited In (5)
- Recurrent neural networks with backtrack-points and negative reinforcement applied to cost-based abduction
- An algorithm for finding MAPs for belief networks through cost-based abduction
- Cost-based abduction and MAP explanation
- An efficient LP-based admissible heuristic for cost-based abduction
- Solving abduction by computing joint explanations. Logic programming formalization, applications to P2P data integration, and complexity results
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)
