The 3-XORSAT threshold
[Le seuil de 3-XORSAT]
Dubois, Olivier1 ; Mandler, Jacques1
1 LIP6, Box 169, CNRS-Université Paris 6, 4 place Jussieu, 75252 Paris cedex 05, France
Comptes Rendus. Mathématique, Tome 335 (2002) no. 11, pp. 963-966.

Nous démontrons l'existence d'un phénomène de seuil pour le problème 3-XORSAT aléatoire (et plus généralement k-XORSAT). Nous fournissons la valeur du seuil comme solution de deux équations transcendantes. Ces résultats confirment rigoureusement ceux obtenus par des physiciens au moyen de la méthode des répliques à un pas de brisure de symétrie et apportent ainsi pour la première fois une preuve de la validité de la méthode des répliques avec brisure sur un problème de la classe des problèmes de satisfaisabilité.

We prove the existence of a threshold phenomenon regarding the random 3-XORSAT problem (or more generally k-XORSAT). We provide the value of the threshold as the solution of two transcendental equations. These results confirm rigorously those obtained by physicists using the one-step replica symmetry breaking method and thus give for the first time the proof of the validity of this method for a problem of the class of satisfiability problems.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/S1631-073X(02)02563-3
Dubois, Olivier 1 ; Mandler, Jacques 1

1 LIP6, Box 169, CNRS-Université Paris 6, 4 place Jussieu, 75252 Paris cedex 05, France 
@article{CRMATH_2002__335_11_963_0,
     author = {Dubois, Olivier and Mandler, Jacques},
     title = {The {3-XORSAT} threshold},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {963--966},
     publisher = {Elsevier},
     volume = {335},
     number = {11},
     year = {2002},
     doi = {10.1016/S1631-073X(02)02563-3},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/S1631-073X(02)02563-3/}
}
TY  - JOUR
AU  - Dubois, Olivier
AU  - Mandler, Jacques
TI  - The 3-XORSAT threshold
JO  - Comptes Rendus. Mathématique
PY  - 2002
SP  - 963
EP  - 966
VL  - 335
IS  - 11
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/S1631-073X(02)02563-3/
DO  - 10.1016/S1631-073X(02)02563-3
LA  - en
ID  - CRMATH_2002__335_11_963_0
ER  - 
%0 Journal Article
%A Dubois, Olivier
%A Mandler, Jacques
%T The 3-XORSAT threshold
%J Comptes Rendus. Mathématique
%D 2002
%P 963-966
%V 335
%N 11
%I Elsevier
%U http://www.numdam.org/articles/10.1016/S1631-073X(02)02563-3/
%R 10.1016/S1631-073X(02)02563-3
%G en
%F CRMATH_2002__335_11_963_0
Dubois, Olivier; Mandler, Jacques. The 3-XORSAT threshold. Comptes Rendus. Mathématique, Tome 335 (2002) no. 11, pp. 963-966. doi : 10.1016/S1631-073X(02)02563-3. http://www.numdam.org/articles/10.1016/S1631-073X(02)02563-3/

[1] Broder, A.Z.; Frieze, A.M.; Upfal, E. On the satisfiability and maximum satisfiability of random 3-CNF formulas, Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, Austin, TX, 1993, pp. 322-330

[2] N. Creignou, H. Daudé, O. Dubois, Approximating the satisfiability threshold for random k-XOR-formulas, 2001, submitted

[3] Franz, S.; Leone, M.; Ricci-Tersenghi, F.; Zecchina, R. Phys. Rev. Lett., 87 (2001), pp. 12713-127209

[4] R. Monasson, personal communication

[5] M. Talagrand, Spin Glasses: A Challenge for Mathematicians, in preparation

[6] Temme, N.M. Asymptotic estimates of Stirling numbers, Studies Appl. Math., Volume 89 (1993), pp. 233-243

[7] Wormald, N.C. Differential equations for random processes and random graphs, Ann. Appl. Probab., Volume 5 (1995), pp. 1217-1235

Cité par Sources :