2008/01/29 by Tu, Ronghui, Mao, Yongyi, Zhao, Jiying
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.0801.4571
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.