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

DOI10.1016/S0004-3702(98)00043-5zbMath0909.68077WikidataQ128081837 ScholiaQ128081837MaRDI 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 (17)

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

This page was built for publication: Approximating MAPs for belief networks is NP-hard and other theorems