Taming Survey Propagation

Опубликовано 7 сентября 2016, 16:01

The Satisfiability problem (SAT) is the problem of assigning a value to a vector x in {0,1}ⁿ of boolean variables so that the falue of a function F(x)=∏_{i=1}^{m}C_{i}(x_{c_{i}})=1. Each c_{i} is a subset of x and each function C_{i} takes the value 1 everywhere but on a single point, where it takes the value 0. Recently, an algorithm called Survey Propagation has been proposed which, along with a decimation procedure, can solve random instances of SAT that are known to be difficult for other algorithms. There has been much discussion regarding the relationship between Survey Propagation (SP) and Belief Propagation (BP). BP takes as inputs a set of variables and a set of kernels, each of which is a likelihood function of a subset of the variables and gives as output an approximation of the a posteriori probability distributions on each variable. If the inputs to BP are x and the kernels are {C_{i}(x_{c_{i}})}, then we call this algorithm na├»ve BP. The Warning Propagation algorithm defines an extended solution space {0,*,1}ⁿ and warning messages on a bipartite graph representing F. If we let the variables be the warning messages defined in WP, and the kernels encode the WP update rules, we can recover the messages defined in SP. Thus we give for the first time (known to us) a way to use BP to recover the dynamics, and not just the statics, of SP.. We give a suggestion as to why it may be easier to find clusters using BP than it is to find individual solutions directly, and thus why SP performs better in the setting of decimation than na├»ve BP. Finally, we give some empirical results comparing SP and Na├»ve BP in the context of the decimation algorithm. This is joint work with Dimitris Achlioptas.