Two solutions to diluted p-spin models and XORSAT problems

被引：160

作者：

Mézard, M ^{[1
]}

Ricci-Tersenghi, F

Zecchina, R

机构：

[1] Univ Paris 11, Lab Phys Theor & Modeles Stat, F-91405 Orsay, France

[2] Univ Roma La Sapienza, Dipartimento Fis, I-00185 Rome, Italy

[3] Univ Roma La Sapienza, INFM, I-00185 Rome, Italy

[4] Int Ctr Theoret Phys, I-34100 Trieste, Italy

来源：

JOURNAL OF STATISTICAL PHYSICS | 2003年 / 111卷 / 3-4期

关键词：

spin glass; satisfiability; leaf removal; cavity method;

D O I：

10.1023/A:1022886412117

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

We derive analytical solutions for p-spin models with finite connectivity at zero temperature. These models are the statistical mechanics equivalent of p-XORSAT problems in theoretical computer science. We give a full characterization of the phase diagram: location of the phase transitions (static and dynamic), together with a description of the clustering phenomenon taking place in configurational space. We use two alternative methods: the cavity approach and a rigorous derivation.

引用

页码：505 / 533

页数：29

共 19 条

[1]

[Anonymous], 1999, RANDOM GRAPHS

[2] Core percolation in random graphs: a critical phenomena analysis [J].

Bauer, M ;

Golinelli, O .

EUROPEAN PHYSICAL JOURNAL B, 2001, 24 (03) :339-352

[3]

BOVIER A, CONDMAT0206562

[4] Complexity transitions in global algorithms for sparse linear systems over finite fields [J].

Braunstein, A ;

Leone, M ;

Ricci-Tersenghi, F ;

Zecchina, R .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 2002, 35 (35) :7559-7574

[5] Rigorous decimation-based construction of ground pure states for spin-glass models on random lattices [J].

Cocco, S ;

Dubois, O ;

Mandler, J ;

Monasson, R .

PHYSICAL REVIEW LETTERS, 2003, 90 (04) :4-472054

[6] Exact solutions for diluted spin glasses and optimization problems [J].

Franz, S ;

Leone, M ;

Ricci-Tersenghi, F ;

Zecchina, R .

PHYSICAL REVIEW LETTERS, 2001, 87 (12) :127209-127209

[7] A ferromagnet with a glass transition [J].

Franz, S ;

Mézard, M ;

Ricci-Tersenghi, F ;

Weigt, M ;

Zecchina, R .

EUROPHYSICS LETTERS, 2001, 55 (04) :465-471

[8] Some optimal inapproximability results [J].

Håstad, J .

JOURNAL OF THE ACM, 2001, 48 (04) :798-859

[9] Phase coexistence and finite-size scaling in random combinatorial problems [J].

Leone, M ;

Ricci-Tersenghi, F ;

Zecchina, R .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 2001, 34 (22) :4615-4626

[10] Statistical mechanics methods and phase transitions in optimization problems [J].

Martin, OC ;

Monasson, R ;

Zecchina, R .

THEORETICAL COMPUTER SCIENCE, 2001, 265 (1-2) :3-67

← 1 2 →