Stephan Mertens - Publications Home | Research | Publications | Teaching | Smorgasbord

Threshold Values of Random K-SAT from the Cavity Method

Stephan Mertens, Marc Mézard and Riccardo Zecchina

---

Abstract

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.

---

BiBTeX Entry

@article{mertens:mezard:zecchina:03,
  author = {Stephan Mertens and Marc M\'ezard and Riccardo Zecchina},
  title = {Threshold Values of Random {K-SAT} from the Cavity Method},
  journal = {Random Structures and Algorithms},
  year = {2006},
  volume = {28},
  issue = {3},
  pages = {340--373},
  doi =  {10.1002/rsa.20090},
  note =  {\url{http://arxiv.org/abs/cs.CC/0309020}}
}

---

Download:
sat1.pdf (pdf, 578 K)