Approximate belief updating in max-2-connected Bayes networks is NP-hard Academic Article uri icon

abstract

  • Page 1. Artificial Intelligence 173 (2009) 1150–1153 Contents lists available at ScienceDirect Artificial Intelligence www.elsevier.com/locate/artint Approximate belief updating in max-2-connected Bayes networks is NP-hard Erez Karpas a,1, Solomon Eyal Shimony b,∗ , Amos Beimel b a Faculty of Industrial Engineering, Technion, Haifa, Israel b Dept. of Computer Science, Ben-Gurion University, PO Box 645, Beer-Sheva, Israel article info abstract Article history: Received 8 September 2008 Received in revised form 16 April 2009 Accepted 25 April 2009 Available online 6 May 2009 Keywords: Bayes network Complexity Max-k-connected 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. © 2009 Elsevier BV All rights reserved. 1. Introduction …

publication date

  • January 1, 2009