Approximating the Unsatisfiability Threshold of Random Formulas

Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)253-269
Number of pages17
JournalRandom Structures and Algorithms
Issue number3
StatePublished - May 1998


  • Approximations
  • Probabilistic method
  • Random formulas
  • Satisfiability
  • Threshold point

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'Approximating the Unsatisfiability Threshold of Random Formulas'. Together they form a unique fingerprint.

Cite this