Approximating the unsatisfiability threshold of random formulas

✍ Scribed by Lefteris M. Kirousis; Evangelos Kranakis; Danny Krizanc; Yannis C. Stamatiou

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 216 KB
• Volume: 12
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199805)12:3<253::aid-rsa3>3.0.co;2-u

✦ Synopsis

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 F 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.601q . In general, by letting the