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

DOI10.1016/J.ARTINT.2009.04.001MaRDI QIDQ840823zbMATH OpenOpenAlexWikidataFDO

Authors E. Karpas, Amos Beimel, Solomon E. 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

Bayes networkcomplexitymax-\(k\)-connected

Mathematics Subject Classification ID

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

Recommendations

• Approximating MAPs for belief networks is NP-hard and other theorems
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing
• Finding MAPs for belief networks is NP-hard
• scientific article; zbMATH DE number 2243356

Cites work

• 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
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• The computational complexity of probabilistic inference using Bayesian belief networks

Cited in

(2)

• Approximating MAPs for belief networks is NP-hard and other theorems
• Approximating probabilistic inference in Bayesian belief networks is NP- hard

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q840823)