Premium
Approximating the unsatisfiability threshold of random formulas
Author(s) -
Kirousis Lefteris M.,
Kranakis Evangelos,
Krizanc Danny,
Stamatiou Yannis C.
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199805)12:3<253::aid-rsa3>3.0.co;2-u
Subject(s) - mathematics , statistics , statistical physics , econometrics , computer science , physics
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