On the K‐sat model with large number of clauses. Issue 3 (26th November 2017) - Panchenko, Dmitry
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 α / 2 K − α c ∗ ( N ) / 2 K up to smaller order terms o ( α ) as α → ∞ uniformly in N, where c ∗ ( N ) is the expected normalized maximum energy of some specific mixed p ‐spin spin glass model. The formula for the limit of c ∗ ( N ) is well known in the theory of spin glasses.