Threshold values of Random K-SAT from the cavity method

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