| Title | The unsatisfiability threshold revisited |
| Authors | Alexis Kaporis, Dept. Computer Engineering
and Informatics - University of Patras (Greece)
Lefteris Kirousis, Dept. Computer Engineering and Informatics - University of Patras (Greece) Yannis Stamatiou, Dept. Computer Eng. and Informatics - University of Patras / Computer Technology Institute - Patras (Greece) Malvina Vamvakari, Dept. Computer Eng. and Informatics - University of Patras / Computer Technology Institute - Patras (Greece) Michele Zito, Dept Computer Science - University of Liverpool (UK) |
| Main Fields | 4. computational complexity |
| Other Main Fields | Probabilistic methods in Computer Science
Applied Combinatorics |
| Abstract + Keywords | The problem of determining the unsatisfiability
threshold for random 3-SAT formulas consists
in determining the clauses to variables 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. The currently best upper bound is 4.506 and has been recently announced by Dubois et al. (but to the best of our knowledge, there is no complete proof available from the authors yet). In this paper, 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 {\em local maximum satisfying truth assignments} can be combined with results for the {\em 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 an upper bound to the $q$-binomial coefficients (a generalization of the binomial coefficients). Despite the extensive literature on properties of these coefficients, no such bounds were previously known. KEYWORDS: Satisfiability, threshold, random allocation. |