Exact solutions for diluted spin glasses and optimization problems

被引:69
作者
Franz, S
Leone, M
Ricci-Tersenghi, F
Zecchina, R
机构
[1] Int Ctr Theoret Phys, Condensed Matter Grp, I-34014 Trieste, Italy
[2] SISSA, I-34014 Trieste, Italy
关键词
D O I
10.1103/PhysRevLett.87.127209
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
We study the low temperature properties of p-spin glass models with finite connectivity and of some optimization problems. Using a one-step functional replica symmetry breaking ansatz we can solve exactly the saddle-point equations for graphs with uniform connectivity. The resulting ground state energy is in perfect agreement with numerical simulations. For fluctuating connectivity graphs, the same ansatz can be used in a variational way: For p-spin models (known as p-XOR-SAT in computer science) it provides the exact configurational entropy together with the dynamical and static critical connectivities (for p = 3, gamma (d) = 0.818, and gamma (s) = 0.918), whereas for hard optimization problems like 3-SAT or Bicoloring it provides new upper bounds for their critical thresholds (gamma (var)(c) = 4.396 and gamma (var)(c) = 2.149).
引用
收藏
页码:127209 / 127209
页数:4
相关论文
共 40 条
[1]  
ACHLIOPTAS D, IN PRESS THEOR COMPU
[2]   FORMATION OF GLASSES FROM LIQUIDS AND BIOPOLYMERS [J].
ANGELL, CA .
SCIENCE, 1995, 267 (5206) :1924-1935
[3]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[4]   A variational description of the ground state structure in random satisfiability problems [J].
Biroli, G ;
Monasson, R ;
Weigt, M .
EUROPEAN PHYSICAL JOURNAL B, 2000, 14 (03) :551-568
[5]   The scaling window of the 2-SAT transition [J].
Bollobás, B ;
Borgs, C ;
Chayes, JT ;
Kim, JH ;
Wilson, DB .
RANDOM STRUCTURES & ALGORITHMS, 2001, 18 (03) :201-256
[6]   CRITICAL-BEHAVIOR OF THE BETHE LATTICE SPIN-GLASS [J].
CARLSON, JM ;
CHAYES, JT ;
CHAYES, L ;
SETHNA, JP ;
THOULESS, DJ .
EUROPHYSICS LETTERS, 1988, 5 (04) :355-360
[7]  
CHAYES JT, 1999, RANDOM STRUCT ALGORI, V15
[8]  
CREIGNOU N, ARXIVCSDM0106001
[9]   REPLICA SYMMETRY-BREAKING IN WEAK CONNECTIVITY SYSTEMS [J].
DEDOMINICIS, C ;
MOTTISHAW, P .
JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1987, 20 (18) :L1267-L1273
[10]  
DUBOIS O, IN PRESS COMPUT SCI