Proof of the satisfiability conjecture for large k
Proceedings of the forty-seventh annual ACM symposium on Theory of computing, 2015•dl.acm.org
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 is
given explicitly by the one-step replica symmetry breaking (1SRB) prediction from statistical
physics. We believe that our methods may apply to a range of random constraint satisfaction
problems in the 1RSB class.
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 is
given explicitly by the one-step replica symmetry breaking (1SRB) prediction from statistical
physics. We believe that our methods may apply to a range of random constraint satisfaction
problems in the 1RSB class.
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 is given explicitly by the one-step replica symmetry breaking (1SRB) prediction from statistical physics. We believe that our methods may apply to a range of random constraint satisfaction problems in the 1RSB class.
ACM Digital Library以上显示的是最相近的搜索结果。 查看全部搜索结果