Name
Abstract | ||
|---|---|---|
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 |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1002/rsa.v28:3 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
cavity approach,satisfiability,random k-sat,phys rev e,k-sat,wiley periodicals,cavity method,average case complexity,inc. random struct,exact satisfiability threshold,threshold phenomenon,survey propagation,large k.,various threshold value,satisfiability threshold,closed expression,analytic solution,phase transition,cavity equation | Journal | 28 |
Issue | Citations | PageRank |
3 | 57 | 4.70 |
References | Authors | |
17 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| steven b mertens | 1 | 57 | 4.70 |
| Marc Mézard | 2 | 590 | 39.09 |
| riccardo zecchina | 3 | 637 | 55.46 |