The threshold for random k-SAT is 2<sup>k</sup> (ln 2 - O(k))
The threshold for random k-SAT is 2<sup>k</sup> (ln 2 - O(k))
Let Fk(n,m) be a random k-SAT formula on n variables formed by selecting uniformly and independently m out of all possible k-clauses. It is well-known that for r ≥ 2k ln 2, Fk(n,rn) is unsatisfiable with probability 1-o(1). We prove that there exists a sequence tk = O(k) such that …