TR-96-09: A Better Upper Bound for the Unsatisfiability Threshold

Let phi be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number kappa such that if the ratio of the number of clauses over the number of variables of phi strictly exceeds kappa, then phi is almost certainly unsatisfiable. By a well known and more or less straightforward argument, it can be shown that kappa leq 5.191. This upper bound was improved by Kamath, Motwani, Palem, and Spirakis to 4.758, by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of kappa is around 4.2. In this work, we show that this upper bound can be improved to 4.667. Our proof is elementary and short, and does not use unverifiable mechanical calculations. Moreover it generalizes in a straightforward manner to k-SAT, for k>3.