On Random 3-sat
A. El Maftouhi, W. Fernandez de la Véga · Combinatorics Probability Computing · 1995
Let S be a set of m clauses each containing three literals chosen at random in a set { p 1 , ¬ p 1 ,…, p n , ¬p n } of n propositional variables and their negations. Let be the set of all such S with m = cn for a fixed c > 0. We show, improving significantly over the first moment upper bound , that if m and n tend to infinity with , then almost all are unsatisfiable.