Approximate belief updating in max-2-connected Bayes networks is NP-hard.
Erez KarpasSolomon Eyal ShimonyAmos BeimelPublished in: Artif. Intell. (2009)
Keyphrases
- belief updating
- bayes networks
- np hard
- graphical models
- constraint networks
- special case
- optimal solution
- bayesian belief networks
- worst case
- approximation algorithms
- bayesian networks
- computational complexity
- constraint satisfaction problems
- belief revision
- lower bound
- np complete
- probabilistic inference
- constraint propagation
- markov networks