Threshold values of Random K-SAT from the cavity method
<|reference_start|>Threshold values of Random K-SAT from the cavity method: 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.<|reference_end|>
@article{mertens2003threshold,
    title={Threshold values of Random K-SAT from the cavity method},
    author={Stephan Mertens, Marc Mezard and Riccardo Zecchina},
    journal={arXiv preprint arXiv:cs/0309020},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0309020},
    primaryClass={cs.CC cond-mat.dis-nn cs.DM}
}