On the $K$-sat model with large number of clauses

Dmitry Panchenko

Published 2016-08-22Version 1

We show that in the $K$-sat model with $N$ variables and $\alpha N$ clauses, the expected ratio of the smallest number of unsatisfied clauses to the number of variables is $\alpha/2^K - \sqrt{\alpha} c_*(N)/2^K$ up to smaller order terms $o(\sqrt{\alpha})$ as $\alpha\to\infty$ 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 from the theory of spin glasses.