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

被引：3
|
作者：
Karpas, Erez [2 ]
Shimony, Solomon Eyal [1 ]
Beimel, Amos [1 ]
机构：
[1] Ben Gurion Univ Negev, Dept Comp Sci, IL-84105 Beer Sheva, Israel
[2] Technion Israel Inst Technol, Fac Ind Engn, Haifa, Israel
来源：
ARTIFICIAL INTELLIGENCE | 2009年 / 173卷 / 12-13期
关键词：
Bayes network; Complexity; Max-k-connected; PROBABILISTIC INFERENCE; COMPLEXITY;
D O I：
10.1016/j.artint.2009.04.001
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
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. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码：1150 / 1153
页数：4
相关论文
共 50 条
12345