The 3-XORSAT threshold

Olivier Dubois; Jacques Mandler

doi:10.1016/S1631-073X(02)02563-3

The 3-XORSAT threshold
[Le seuil de 3-XORSAT]

Olivier Dubois ¹ ; Jacques Mandler ¹

¹ LIP6, Box 169, CNRS-Université Paris 6, 4 place Jussieu, 75252 Paris cedex 05, France

Comptes Rendus. Mathématique, Volume 335 (2002) no. 11, pp. 963-966.

Résumé
Abstract

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 : 2002-08-20
Accepté le : 2002-09-13
Publié le : 2002-10-05

DOI : 10.1016/S1631-073X(02)02563-3

Affiliations des auteurs :

Olivier Dubois ¹ ; Jacques Mandler ¹

¹ LIP6, Box 169, CNRS-Université Paris 6, 4 place Jussieu, 75252 Paris cedex 05, France

@article{CRMATH_2002__335_11_963_0,
     author = {Olivier Dubois and Jacques Mandler},
     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},
}

TY  - JOUR
AU  - Olivier Dubois
AU  - Jacques Mandler
TI  - The 3-XORSAT threshold
JO  - Comptes Rendus. Mathématique
PY  - 2002
SP  - 963
EP  - 966
VL  - 335
IS  - 11
PB  - Elsevier
DO  - 10.1016/S1631-073X(02)02563-3
LA  - en
ID  - CRMATH_2002__335_11_963_0
ER  -

%0 Journal Article
%A Olivier Dubois
%A Jacques Mandler
%T The 3-XORSAT threshold
%J Comptes Rendus. Mathématique
%D 2002
%P 963-966
%V 335
%N 11
%I Elsevier
%R 10.1016/S1631-073X(02)02563-3
%G en
%F CRMATH_2002__335_11_963_0

Olivier Dubois; Jacques Mandler. The 3-XORSAT threshold. Comptes Rendus. Mathématique, Volume 335 (2002) no. 11, pp. 963-966. doi : 10.1016/S1631-073X(02)02563-3. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/S1631-073X(02)02563-3/

Bibliographie
Cité par

[1] A.Z. Broder; A.M. Frieze; E. Upfal 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] S. Franz; M. Leone; F. Ricci-Tersenghi; R. Zecchina 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] N.M. Temme Asymptotic estimates of Stirling numbers, Studies Appl. Math., Volume 89 (1993), pp. 233-243

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

Cité par Sources :

Commentaires - Politique