Approximate belief updating in max-2-connected Bayes networks is NP-hard

DOI10.1016/J.ARTINT.2009.04.001zbMath1191.68683OpenAlexW2038679483WikidataQ57518737 ScholiaQ57518737MaRDI QIDQ840823

Erez Karpas, Amos Beimel, Solomon Eyal Shimony

Publication date: 14 September 2009

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

Full work available at URL: https://doi.org/10.1016/j.artint.2009.04.001

zbMATH Keywords

complexityBayes networkmax-\(k\)-connected

Mathematics Subject Classification ID

Reasoning under uncertainty in the context of artificial intelligence (68T37) Logic programming (68N17)

Cites Work

• Unnamed Item
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks
• Finding MAPs for belief networks is NP-hard
• The computational complexity of probabilistic inference using Bayesian belief networks

This page was built for publication: Approximate belief updating in max-2-connected Bayes networks is NP-hard