TY - GEN

T1 - Coupon collectors, q-binomial coefficients and the unsatisfiability threshold

AU - Kaporis, Alexis C.

AU - Kirousis, Lefteris M.

AU - Stamatiou, Yannis C.

AU - Vamvakari, Malvina

AU - Zito, Michele

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - 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. in 1999 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 withresu lts for coupon collector’s probabilities 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 may be of independent interest.

AB - 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. in 1999 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 withresu lts for coupon collector’s probabilities 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 may be of independent interest.

UR - http://www.scopus.com/inward/record.url?scp=84962798211&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84962798211&partnerID=8YFLogxK

U2 - 10.1007/3-540-45446-2_21

DO - 10.1007/3-540-45446-2_21

M3 - Conference contribution

AN - SCOPUS:84962798211

SN - 9783540454465

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 328

EP - 338

BT - Theoretical Computer Science - 7th Italian Conference, ICTCS 2001, Proceedings

A2 - Restivo, Antonio

A2 - Rocca, Simona Ronchi Della

A2 - Roversi, Luca

PB - Springer Verlag

T2 - 7th Italian Conference on Theoretical Computer Science, ICTCS 2001

Y2 - 4 October 2001 through 6 October 2001

ER -