Approximating the Unsatisfiability Threshold of Random Formulas

Let φ be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number κ such that if the ratio of the number of clauses over the number of variables of φ strictly exceeds κ, then φ is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that κ ≤ 5.191. This upper bound was improved by Kamath et al. to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of κ is around 4.2. In this work, we define, in terms of the random formula φ, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then φ 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 κ equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601+. 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 κ This technique generalizes in a straightforward manner to k-SAT for k > 3.