Approximating cost-based abduction is NP-hard

摘要

Cost-based abduction (CBA) is an important problem in reasoning under uncertainty. Finding Least-Cost Proofs (LCPs) for CBA systems is known to be NP-hard and has been a subject of considerable research over the past decade. In this paper, we show that approximating LCPs, within a fixed ratio bound of the optimal solution, is NP-hard, even for quite restricted subclasses of CBAs. We also consider a related problem concerned with the fine-tuning of a CBA's cost function.