Proof of the satisfiability conjecture for large $k$


We establish the satisfiability threshold for random k-SAT for all $k\ge k_0$, with $k_0$ an absolute constant. That is, there exists a limiting density $\alpha_{\mathrm{SAT}}(k)$ such that a random k-SAT formula of clause density $\alpha$ is with high probability satisfiable for $\alpha\lt\alpha_{\mathrm{SAT}}$, and unsatisfiable for
$\alpha>\alpha_{\mathrm{SAT}}$. We show that the threshold $\alpha_{\mathrm{SAT}}(k)$ is given explicitly by the one-step replica symmetry breaking prediction from statistical physics. The proof develops a new analytic method for moment calculations on random graphs, mapping a high-dimensional optimization problem to a more tractable problem of analyzing tree recursions. We believe that our method may apply to a range of random CSPs in the 1-RSB universality class.


Jian Ding

Department of Statistics and Data Science, University of Pennsylvania, Philadelphia, PA

Allan Sly

Department of Mathematics, Princeton University, Princeton, NJ

Nike Sun

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA