nips nips2004 nips2004-41 nips2004-41-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Erik Aurell, Uri Gordon, Scott Kirkpatrick
Abstract: 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 derivation of survey propagation, belief propagation and several interesting hybrid methods. We then present numerical experiments which use WSAT (a widely used random-walk based SAT solver) to quantify the complexity of the 3-SAT formulae as a function of their parameters, both as randomly generated and after simpli£cation, 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 number 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 hardSAT regime appears to re¤ect 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 practical algorithm development. 1
[1] M´ zard M., Parisi G. & Zecchina R.. (2002) Analytic and Algorithmic Solutions of Random e Satis£ability Problems. Science, 297:812-815
[2] M´ zard M. & Zecchina R. (2002) The random K-satis£ability problem: from an analytic solue tion to an ef£cient algorithm. Phys. Rev. E 66: 056126.
[3] Braunstein A., Mezard M. & Zecchina R., “Survey propagation: an algorithm for satis£ability”, arXiv:cs.CC/0212002 (2002).
[4] Parisi G. (2003), On the probabilistic approach to the random satis£ability problem, Proc. SAT 2003 and arXiv:cs:CC/0308010v1 .
[5] Braunstein A. and Zecchina R., (2004) Survey Propagation as Local Equilibrium Equations. arXiv:cond-mat/0312483 v5.
[6] Pearl J. (1988) Probabilistic Reasoning in Intelligent Systems, 2nd Edition, Kauffmann.
[7] Kirkpatrick S. & Selman B. (1994) Critical Behaviour in the Sati£ability of Random Boolean Expressions. Science 264: 1297-1301.
[8] Monasson R. & Zecchina R. (1997) Statistical mechanics of the random K-Sat problem. Phys. Rev. E 56: 1357–1361.
[9] Montanari A., Parisi G. & Ricci-Tersenghi F. (2003) Instability of one-step replica-symmetricbroken phase in satis£ability problems. cond-mat/0308147.
[10] Papadimitriou C.H. (1991). In FOCS 1991, p. 163.
[11] Selman B. & Kautz H.A. (1993) In Proc. AAAI-93 26, pp. 46-51.
[12] Semerjian G. & Monasson R. (2003). Phys Rev E 67: 066103.
[13] Barthel W., Hartmann A.K. & Weigt M. (2003). Phys. Rev. E 67: 066104.
[14] Selman B., Kautz K. & Cohen B. (1996) Local Search Strategies for Satis£ability Testing. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26.
[15] http://www.cs.washington.edu/homes/kautz/walksat/