Proof of the satisfiability conjecture for large k

• 成果类型: Article
• 署名作者: Ding, Jian; Sly, Allan; Sun, Nike
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2022.196.1.1
• 发表日期: 2022
• 页码: 1-388
• 关键词: order-parameter; spin-glasses; sat; threshold; models; bounds; propagation; algorithm; number

摘要

We establish the satisfiability threshold for random k-SAT for all k >= k(0), with k(0) an absolute constant. That is, there exists a limiting density alpha(sat) (k) such that a random k-SAT formula of clause density alpha is with high probability satisfiable for alpha < alpha(sat), and unsatisfiable for alpha > alpha(sat). We show that the threshold alpha(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.