Random K -satisfiability problem: From an analytic solution to an efficient algorithm
作者： Marc Mézard , Riccardo Zecchina
DOI: 10.1103/PHYSREVE.66.056126
关键词:
摘要: … They are the closest physical analogues of the satisfiability problems which we study here 23. K-SAT: All interactions involve K spins, and the energy of an interaction node a involving …
arxiv.org
harvard.edu
arxiv-vanity.com参考文章(27)
Rémi Monasson, Riccardo Zecchina, ENTROPY OF THE K-SATISFIABILITY PROBLEM Physical Review Letters. ,vol. 76, pp. 3881- 3885 ,(1996) , 10.1103/PHYSREVLETT.76.3881
Rémi Monasson, Riccardo Zecchina, Statistical mechanics of the randomK-satisfiability model Physical Review E. ,vol. 56, pp. 1357- 1370 ,(1996) , 10.1103/PHYSREVE.56.1357
S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by Simulated Annealing Science. ,vol. 220, pp. 671- 680 ,(1983) , 10.1126/SCIENCE.220.4598.671
Vladimír Černý, Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm Journal of Optimization Theory and Applications. ,vol. 45, pp. 41- 51 ,(1985) , 10.1007/BF00940812
M. Mézard, G. Parisi, Replicas and optimization Journal de Physique Lettres. ,vol. 46, pp. 771- 778 ,(1985) , 10.1051/JPHYSLET:019850046017077100
David J. Aldous, The ζ (2) limit in the random assignment problem Random Structures and Algorithms. ,vol. 18, pp. 381- 418 ,(2001) , 10.1002/RSA.1015
Y Fu, P W Anderson, Application of statistical mechanics to NP-complete problems in combinatorial optimisation Journal of Physics A. ,vol. 19, pp. 1605- 1620 ,(1986) , 10.1088/0305-4470/19/9/033
Leonid A. Levin, Average case complete problems SIAM Journal on Computing. ,vol. 15, pp. 285- 286 ,(1986) , 10.1137/0215020
S. Kirkpatrick, B. Selman, Critical Behavior in the Satisfiability of Random Boolean Expressions Science. ,vol. 264, pp. 1297- 1301 ,(1994) , 10.1126/SCIENCE.264.5163.1297
Marc Mézard, Giorgio Parisi, Riccardo Zecchina, Analytic and Algorithmic Solution of Random Satisfiability Problems Science. ,vol. 297, pp. 812- 815 ,(2002) , 10.1126/SCIENCE.1073287