## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 253-269 |

Number of pages | 17 |

Journal | Random Structures and Algorithms |

Volume | 12 |

Issue number | 3 |

DOIs | |

State | Published - May 1998 |

## Keywords

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

## ASJC Scopus subject areas

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