Proof of the satisfiability conjecture for large k

Jian Ding, Allan Sly, Nike Sun

Research output: Chapter in Book/Report/Conference proceedingConference contribution

89 Scopus citations

Abstract

We establish the satisfiability threshold for random k-SAT for all k ≥ k0. That is, there exists a limiting density αs(k) such that a random k-SAT formula of clause density α is with high probability satisfiable for α < αs, and unsatisfiable for α > αs. The satisfiability threshold αs(k) is given explicitly by the one-step replica symmetry breaking (1rsb) prediction from statistical physics. We believe that our methods may apply to a range of random constraint satisfaction problems in the 1RSB class.

Original languageEnglish (US)
Title of host publicationSTOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages59-68
Number of pages10
ISBN (Electronic)9781450335362
DOIs
StatePublished - Jun 14 2015
Externally publishedYes
Event47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States
Duration: Jun 14 2015Jun 17 2015

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume14-17-June-2015
ISSN (Print)0737-8017

Other

Other47th Annual ACM Symposium on Theory of Computing, STOC 2015
CountryUnited States
CityPortland
Period6/14/156/17/15

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Belief propagation
  • Condensation
  • Constraint satisfaction problem
  • Random k-SAT
  • Replica symmetry breaking
  • Satisfiability threshold
  • Survey propagation

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

Cite this