Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold

2003/10/09 by Dimitris Achlioptas, Cristopher Moore, Achlioptas, Dimitris +1 · 3 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #cond-mat.stat-mech #cs.CC #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.cond-mat/0310227

arxiv created 2003/10/09 · arxiv updated 2009/12/01

Abstract

Many NP-complete constraint satisfaction problems appear to undergo a "phase transition'' from solubility to insolubility when the constraint density passes through a critical threshold. In all such cases it is easy to derive upper bounds on the location of the threshold by showing that above a certain density the first moment (expectation) of the number of solutions tends to zero. We show that in the case of certain symmetric constraints, considering the second moment of the number of solutions yields nearly matching lower bounds for the location of the threshold. Specifically, we prove that the threshold for both random hypergraph 2-colorability (Property B) and random Not-All-Equal k-SAT is 2^k-1 ln 2 -O(1). As a corollary, we establish that the threshold for random k-SAT is of order Theta(2^k), resolving a long-standing open problem.

Cited by

• A Slice-Rank Drift Bound for Random Quantum \(k\)-SAT
• The satisfiability threshold and solution space of random uniquely extendable constraint satisfaction problems
• Symmetric Rule-Based Achlioptas Processes for Random k-SAT

Related

• The Satisfiability Threshold for a Seemingly Intractable Random\n Constraint Satisfaction Problem
• Upper bounds on the 2-colorability threshold of random d-regular k-uniform hypergraphs for k≥ 3
• Proof of the satisfiability conjecture for large k
• Satisfiability threshold for random regular NAE-SAT
• Reconstruction and Clustering in Random Constraint Satisfaction Problems