Approximating MAPs for belief networks is NP-hard and other theorems

DOI10.1016/S0004-3702(98)00043-5zbMath0909.68077MaRDI QIDQ1274288

Sandra M. Hedetniemi, Ashraf M. Abdelbar

Publication date: 12 January 1999

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

zbMATH Keywords

complexityuncertaintysatisfiabilityBayesian belief networksprobabilistic reasoningdynamic abductionnext-best explanation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Understanding the role of noise in stochastic local search: analysis and experiments, Approximating Alternative Solutions, Portfolios in stochastic local search: efficiently computing most probable explanations in Bayesian networks, Most probable explanations in Bayesian networks: complexity and tractability, A computational-level explanation of the speed of goal inference, Rational analysis, intractability, and the prospects of `as if'-explanations, Intractability and approximation of optimization theories of cognition, Multi-dimensional classification with Bayesian networks, Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering, A machine learning approach to algorithm selection for \(\mathcal{NP}\)-hard optimization problems: a case study on the MPE problem, Understanding the scalability of Bayesian network inference using clique tree growth curves, Most frugal explanations in Bayesian networks, The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks, The complexity of approximating MAPs for belief networks with bounded probabilities, Unnamed Item, Evaluation of Bayesian networks with flexible state-space abstraction methods, Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Fusion, propagation, and structuring in belief networks
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• On the ratio of optimal integral and fractional covers
• A linear constraint satisfaction approach to cost-based abduction
• Cost-based abduction and MAP explanation
• Finding MAPs for belief networks is NP-hard
• The complexity of approximating MAPs for belief networks with bounded probabilities
• The computational complexity of probabilistic inference using Bayesian belief networks
• Belief networks revisited