Premium
Threshold values of random K ‐SAT from the cavity method
Author(s) -
Mertens Stephan,
Mézard Marc,
Zecchina Riccardo
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20090
Subject(s) - satisfiability , conjecture , mathematics , computation , stability (learning theory) , random variable , variable (mathematics) , discrete mathematics , combinatorics , mathematical analysis , algorithm , computer science , statistics , machine learning
Using the cavity equations of Mézard, Parisi, and Zecchina Science 297 (2002), 812; Mézard and Zecchina, Phys Rev E 66 (2002), 056126 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 ≥ 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.© 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006