greenline
rgstripes
Otto-Bild Stephan Mertens - Publications
Home | Research | Publications | Teaching | Smorgasbord
greenline

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)

greenline
rgstripes
top Home | Research | Publications | Teaching | Smorgasbord
greenline

© by Stephan Mertens
URL: http://
updated on Thursday, April 27th 2006, 12:47:38 CET;