Bounding the unsatisfiability threshold of random 3-SAT
Svante Janson, Yannis C. Stamatiou, Malvina G. Vamvakari · Random Structures and Algorithms · 2000
The satisfiability threshold conjecture states that for a randomly generated formula of m clauses of exactly k literals over n variables, the probability that it is satisfiable, as n tends to infinity, changes abruptly from 1 to 0, as the ratio r=m/n is increased past a specific value that depends on k alone. The opposite behavior is observed if this ratio is slightly decreased below this value. For k=2, this value exists and it is equal to 1 while for k>2 its existence remains open. For k=3, it is rigorously shown that if it exists, it falls between 3.003 and 4.6011 while experiments place it to, about, 4.2. In this paper, we lower the upper bound to 4.596 through two different approaches. In both approaches, we start with a sum over all truth assignments that appears in an upper bound to the the probability that a random 3-SAT formula is satisfiable. In the first approach, this sum is reformulated as the partition function of a spin system consisting of n sites each of which may assume the values 0 or 1. We then obtain the value 4.596 from an asymptotic expression for this function that results from the application of an optimization technique from statistical physics. In the second approach, we use a connection of the same sum with the Rogers–Szegö polynomials. We obtain the value 4.596 by applying a general technique that exploits a generating function of these polynomials and provides upper bounds for each one of them. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 103–116, 2000