Approximating the unsatisfiability threshold of random formulas
Lefteris M. Kirousis, Evangelos Kranakis, Danny Kriz̧anc, Yannis C. Stamatiou · Random Structures and Algorithms · 1998
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. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 253–269, 1998