TY - JOUR
T1 - The unsatisfiability threshold revisited
AU - Kaporis, Alexis C.
AU - Kirousis, Lefteris M.
AU - Stamatiou, Yannis C.
AU - Vamvakari, Malvina
AU - Zito, Michele
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. 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 show 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.
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. 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 show 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.
KW - Complexity
KW - Phase transition
KW - Probabilistic analysis
KW - Satisfiability
UR - http://www.scopus.com/inward/record.url?scp=34247103776&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34247103776&partnerID=8YFLogxK
U2 - 10.1016/S1571-0653(04)00315-4
DO - 10.1016/S1571-0653(04)00315-4
M3 - Article
AN - SCOPUS:34247103776
SN - 1571-0653
VL - 9
SP - 81
EP - 95
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
ER -