Autor:	Tu, Ronghui, Mao, Yongyi, Zhao, Jiying
Rok vydání:	2008
Předmět:	Computer Science - Information Theory
Druh dokumentu:	Working Paper
Popis:	The Survey Propagation (SP) algorithm for solving $k$-SAT problems has been shown recently as an instance of the Belief Propagation (BP) algorithm. In this paper, we show that for general constraint-satisfaction problems, SP may not be reducible from BP. We also establish the conditions under which such a reduction is possible. Along our development, we present a unification of the existing SP algorithms in terms of a probabilistically interpretable iterative procedure -- weighted Probabilistic Token Passing. Comment: 77 page double-spaced single-column submitted version to IEEE Transactions on Information Theory
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/0801.4571 Zobrazit plný text záznamu View this record from Arxiv