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. To cite this article: O. Dubois, J. Mandler, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 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é. Pour citer cet article : O. Dubois, J. Mandler, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 963-966.