Part of Advances in Neural Information Processing Systems 17 (NIPS 2004)
Erik Aurell, Uri Gordon, Scott Kirkpatrick
Survey propagation is a powerful technique from statistical physics that has been applied to solve the 3-SAT problem both in principle and in practice. We give, using only probability arguments, a common deriva- tion of survey propagation, belief propagation and several interesting hy- brid methods. We then present numerical experiments which use WSAT (a widely used random-walk based SAT solver) to quantify the complex- ity of the 3-SAT formulae as a function of their parameters, both as ran- domly generated and after simplication, guided by survey propagation. Some properties of WSAT which have not previously been reported make it an ideal tool for this purpose its mean cost is proportional to the num- ber of variables in the formula (at a xed ratio of clauses to variables) in the easy-SAT regime and slightly beyond, and its behavior in the hard- SAT regime appears to reect the underlying structure of the solution space that has been predicted by replica symmetry-breaking arguments. An analysis of the tradeoffs between the various methods of search for satisfying assignments shows WSAT to be far more powerful than has been appreciated, and suggests some interesting new directions for prac- tical algorithm development.