Stephan Mertens 1, Marc Mezard 2, Riccardo Zecchina 3
Random Structures and Algorithms 28 (2006) 340-373
Using the cavity equations of \cite{mezard:parisi:zecchina:02,mezard:zecchina:02}, we derive the various threshold values for the number of clauses per variable of the random $K$-satisfiability problem, generalizing the previous results to $K \ge 4$. We also give an analytic solution of the equations, and some closed expressions for these thresholds, in an expansion around large $K$. The stability of the solution is also computed. For any $K$, the satisfiability threshold is found to be in the stable region of the solution, which adds further credit to the conjecture that this computation gives the exact satisfiability threshold.
- 1. Institut für Theoretische Physik,
Otto-von-Guericke Universitat - 2. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
CNRS : UMR8626 – Université Paris XI – Paris Sud - 3. ICTP,
the Abdus Salam International Centre for Theoretical Physics