TR-96-27: Approximating the Unsatisfiability Threshold of Random Formulas

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 define, in terms of the random formula phi, a decreasing sequence of random variables such that if the expected value of any one of them converges to zero, then phi is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for kappa equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.598. In general, by letting the expected value of further terms of this sequence converge to zero, one can, if the calculations are performed, obtain even better approximations to kappa. This technique generalizes in a straightforward manner to k-SAT, for k>3.

TR-96-27.pdf