On the $K$-sat model with large number of clauses
Dmitry Panchenko · arXiv (Cornell University) · 2016
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 - \sqrtα c_*(N)/2^K$ up to smaller order terms $o(\sqrtα)$ as $α\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 in the theory of spin glasses.