Bounding the unsatisfiability threshold of random 3-SAT

The satisfiability threshold conjecture states that fur a randomly generate d formula of m clauses of exactly k literals over n variables, the probabil ity that it is satisfiable, as n tends to infinity, changes abruptly from I to 0, as the ratio I = m/n is increased past a specific value that depends on It alone. The opposite behavior is observed if this ratio is slightly d ecreased below this value. For k = 2, this value exists and it is equal to 1 while for Ci > 2 its existence remains open. For ii = 3, it is rigorously shown that if it exists: it falls between 3.003 and 4.6011 while experimen ts place it to, about, 4.2. In this paper, we lower the upper bound to 4.59 6 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 proba bility that a random 3-SAT formula is satisfiable. In the first approach, t his sum is reformulated as the partition function of a spin system consisti ng of n sites each of which may assume the values 0 or 1. We then obtain th e 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 Roger s-Szego polynomials. We obtain the value 4.596 by applying a general techni que that exploits a generating function of these polynomials and provides u pper bounds for each one of them. (C) 2000 John Wiley & Sons, Inc.