On the K‐sat model with large number of clauses
- 26 November 2017
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 52 (3) , 536-542
Abstract
We show that in the K‐sat model with N variables and αN clauses, the expected ratio of the smallest number of unsatisfied clauses to the number of variables is up to smaller order terms as uniformly in N, where is the expected normalized maximum energy of some specific mixed p‐spin spin glass model. The formula for the limit of is well known in the theory of spin glasses.Keywords
All Related Versions
Funding Information
- NSERC
This publication has 20 references indexed in Scilit:
- The Parisi ultrametricity conjectureAnnals of Mathematics, 2013
- The Parisi formulaAnnals of Mathematics, 2006
- Threshold values of random K‐SAT from the cavity methodRandom Structures & Algorithms, 2005
- Random MAX SAT, random MAX CUT, and their phase transitionsRandom Structures & Algorithms, 2004
- The High Temperature Region of the Viana–Bray Diluted Spin Glass ModelJournal of Statistical Physics, 2004
- Bounds for diluted mean-fields spin glass modelsProbability Theory and Related Fields, 2004
- Broken Replica Symmetry Bounds in the Mean Field Spin Glass ModelCommunications in Mathematical Physics, 2003
- Analytic and Algorithmic Solution of Random Satisfiability ProblemsScience, 2002
- A sequence of approximated solutions to the S-K model for spin glassesJournal of Physics A: General Physics, 1980
- Infinite Number of Order Parameters for Spin-GlassesPhysical Review Letters, 1979