Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
Authors:
- Dimitris AchlioptasDADimitris Achlioptas
- Cristopher MooreCMCristopher Moore
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 36 (3) , 740-762
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.
Keywords
All Related Versions
This publication has 39 references indexed in Scilit:
- The two possible values of the chromatic number of a random graphAnnals of Mathematics, 2005
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)Journal of the American Mathematical Society, 2004
- A sharp threshold in proof complexity yields lower bounds for satisfiability searchJournal of Computer and System Sciences, 2004
- Two‐coloring random hypergraphsRandom Structures & Algorithms, 2002
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT FormulaeJournal of Algorithms, 1997
- On Random 3-satCombinatorics, Probability and Computing, 1995
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problemInformation Sciences, 1990
- Many hard examples for resolutionJournal of the ACM, 1988
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability ProblemSIAM Journal on Computing, 1986
- On 3-chromatic hypergraphsDiscrete Mathematics, 1978