TY - GEN

T1 - Approximating the unsatisfiability threshold of random formulas

T2 - 4th European Symposium on Algorithms, ESA 1996

AU - Kirousis, Lefteris M.

AU - Kranakis, Evangelos

AU - Krizanc, Danny

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.

PY - 1996

Y1 - 1996

N2 - 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, 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 κ 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. 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 κ. This technique generalizes in a straightforward manner to k-SAT, for k > 3.

AB - 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, 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 κ 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. 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 κ. This technique generalizes in a straightforward manner to k-SAT, for k > 3.

UR - http://www.scopus.com/inward/record.url?scp=84958038313&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958038313&partnerID=8YFLogxK

U2 - 10.1007/3-540-61680-2_44

DO - 10.1007/3-540-61680-2_44

M3 - Conference contribution

AN - SCOPUS:84958038313

SN - 3540616802

SN - 9783540616801

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 27

EP - 38

BT - Algorithms - ESA 1996 - 4th Annual European Symposium, Proceedings

A2 - Diaz, Josep

A2 - Serna, Maria

PB - Springer Verlag

Y2 - 25 September 1996 through 27 September 1996

ER -