The asymptotic order of the random k-SAT threshold
Dimitris Achlioptas, Cristopher Moore · 2003
Form a random k-SAT formula on n variables by selecting uniformly and independently m=rn clauses out of all 2/sup k/ (/sub k//sup n/) possible k-clauses. The satisfiability threshold conjecture asserts that for each k there exists a constant r/sub k/ such that, as n tends to infinity, the probability that the formula is satisfiable tends to 1 if rr/sub k/. It has long been known that 2/sup k//k2/sup k-1/ ln 2-d/sub k/, where d/sub k//spl rarr/(1+ln2)/2. Our proof also allows a blurry glimpse of the "geometry" of the set of satisfying truth assignments.