The 3-XORSAT threshold
Authors:
- Olivier DuboisODOlivier Dubois
- Jacques MandlerJMJacques Mandler
Open Access
- 1 December 2002
- journal article
- Published by MathDoc/Centre Mersenne in Comptes Rendus Mathematique
- Vol. 335 (11) , 963-966
Abstract
National audienceWe 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 problemsKeywords
This publication has 2 references indexed in Scilit:
- Differential Equations for Random Processes and Random GraphsThe Annals of Applied Probability, 1995
- Asymptotic Estimates of Stirling NumbersStudies in Applied Mathematics, 1993