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.
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é.
Accepted:
Published online:
Olivier Dubois 1; Jacques Mandler 1
@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}, }
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/
[1] 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] 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] Asymptotic estimates of Stirling numbers, Studies Appl. Math., Volume 89 (1993), pp. 233-243
[7] Differential equations for random processes and random graphs, Ann. Appl. Probab., Volume 5 (1995), pp. 1217-1235
Cited by Sources:
Comments - Policy