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

作者：

Highlights：

•

摘要

A max-2-connected Bayes network is one where there are at most 2 distinct directed paths between any two nodes. We show that even for this restricted topology, null-evidence belief updating is hard to approximate.

论文关键词：Bayes network,Complexity,Max-k-connected

论文评审过程：Received 8 September 2008, Revised 16 April 2009, Accepted 25 April 2009, Available online 6 May 2009.

论文官网地址：https://doi.org/10.1016/j.artint.2009.04.001