Proof of the satisfiability conjecture for large k

Jian Ding, Allan Sly, Nike Sun

Research output: Contribution to journalArticlepeer-review

Abstract

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

Original languageEnglish (US)
Pages (from-to)1-388
Number of pages388
JournalAnnals of Mathematics
Volume196
Issue number1
DOIs
StatePublished - Jul 2022

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Boolean satisfiability
  • Random constraint satisfaction problem
  • Replica symmetry breaking
  • Spin glasses
  • Warning propagation

Fingerprint

Dive into the research topics of 'Proof of the satisfiability conjecture for large k'. Together they form a unique fingerprint.

Cite this