Combinatorics, Probability and Computing

Research Article

On Random 3-sat

A. El Maftouhia1 and W. Fernandez De La Vegaa1

a1 Laboratoire de Recherche en Informatique, Universite de paris-Sud, Bât. 490, 91405 Orsay Cedex, France

Abstract

Let S be a set of m clauses each containing three literals chosen at random in a set {p1, ¬p1,…,pn, ¬pn} of n propositional variables and their negations. Let S0963548300001590inline1 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 S0963548300001590inline2, that if m and n tend to infinity with S0963548300001590inline3, then almost all S0963548300001590inline4 are unsatisfiable.

(Received February 11 1994)

(Revised October 31 1994)