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

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