A variational description of the ground state structure in random satisfiability problems

被引:102
作者
Biroli, G [1 ]
Monasson, R [1 ]
Weigt, M [1 ]
机构
[1] Ecole Normale Super, Phys Theor Lab, CNRS, F-75231 Paris 05, France
关键词
D O I
10.1007/s100510051065
中图分类号
O469 [凝聚态物理学];
学科分类号
070205 ;
摘要
A variational approach to finite connectivity spin-glass-like models is developed and applied to describe the structure of optimal solutions in random satisfiability problems. Our variational scheme accurately reproduces the known replica symmetric results and also allows for the inclusion of replica symmetry breaking effects. For the 3-SAT problem, we find two transitions as the ratio alpha of logical clauses per Boolean variables increases. At the first one alpha(s) similar or equal to 3.96, a non-trivial organization of the solution space in geometrically separated clusters emerges. The multiplicity of these clusters as well as the typical distances between different solutions are calculated. At the second threshold alpha(c) similar or equal to 4.48, satisfying assignments disappear and a finite fraction B-o similar or equal to 0.13 of variables are overconstrained and take the same values in all optimal (though unsatisfying) assignments. These values have to be compared to alpha(c) similar or equal to 4.27, B-o similar or equal to 0.4 obtained from numerical experiments on small instances. Within the present variational approach, the SAT-UNSAT transition naturally appears as a mixture of a first and a second order transition. For the mixed 2 + p-SAT with p < 2/5, the behavior is as: expected much simpler: a unique smooth transition from SAT to UNSAT takes place at alpha(c) = 1/(1 - p).
引用
收藏
页码:551 / 568
页数:18
相关论文
共 40 条
[1]  
ACHILIOPTAS D, 1997, P RALCOM 7, P1
[2]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[3]   MULTIFRACTALITY IN FORGETFUL MEMORIES [J].
BEHN, U ;
VANHEMMEN, JL ;
KUHN, R ;
LANGE, A ;
ZAGREBNOV, VA .
PHYSICA D, 1993, 68 (3-4) :401-415
[4]  
BOUCHAUD J.-P., 1998, SPIN GLASSES RANDOM
[5]  
BRODER AZ, 1993, PROCEEDINGS OF THE FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P322
[6]  
CHANTAL V, 1992, P 33 IEEE S FDN COMP, P620
[7]  
Cheeseman P C., 1991, INT JOINT C ARTIFICI, V91, P331
[8]   Analytical and numerical study of internal representations in multilayer neural networks with binary weights [J].
Cocco, S ;
Monasson, R ;
Zecchina, R .
PHYSICAL REVIEW E, 1996, 54 (01) :717-725
[9]  
COCCO S, 1995, THESIS ROMA
[10]   LONDON-BAHRAIN ARCHAEOLOGICAL EXPEDITION - EXCAVATIONS AT SAAR 1991 [J].
CRAWFORD, H .
ARABIAN ARCHAEOLOGY AND EPIGRAPHY, 1993, 4 (01) :1-19