ALCOMFT-TR-01-103

Alexis Kaporis, Lefteris Kirousis, Yannis Stamatiou, Malvina Vamvakari and Michele Zito
The unsatisfiability threshold revisited
Patras. Work package 4. May 2001.

Abstract: \beginabstract The problem of determining the unsatisfiability threshold for random 3-SAT formulas consists in determining the clause to variable ratio that marks the experimentally observed abrupt change from almost surely satisfiable formulas to almost surely unsatisfiable. Up to now, there have been rigorously established increasingly better lower and upper bounds to the actual threshold value. An upper bound of 4.506 was announced by Dubois et al. but, to the best of our knowledge, no complete proof has been made available from the authors yet. We consider the problem of bounding the threshold value from above using methods that, we believe, are of interest on their own right. More specifically, we explain how the method of local maximum satisfying truth assignments can be combined with results for the occupancy problem in random allocation schemes of balls into bins in order to achieve an upper bound for the unsatisfiability threshold less than 4.571. Thus, we improve over the best, with an available complete proof, previous upper bound, which was 4.596. In order to obtain this value, we also establish a bound on the q-binomial coefficients (a generalization of the binomial coefficients) which, we believe, is of independent interest. \endabstract

Postscript file: ALCOMFT-TR-01-103.ps.gz (81 kb).