Threshold values of random  K ‐SAT from the cavity method | Zendy

Mertens Stephan | Zendy; Mézard Marc | Zendy; Zecchina Riccardo | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research