Abstract:
$k$-SAT is one of the best known among a wide class of random constraint satisfaction problems believed to exhibit a threshold phenomenon where the control parameter is the ratio, number of constraints to number of variables. There has been a large amount of work towards estimating the 3-SAT threshold. We present a new \emph {structural} (or \emph{syntactic}) approach aimed at narrowing the gap between the exact threshold and upper bounds obtained by the first moment method. This is based on the notion of \emph{typicity}, specific definitions of which may vary so as to encompass any purely formal property of a random formula which holds with high probability. The idea is that the formulae responsible for the gap tend to be atypical, hence restriction to typical formulae will give a better bound. In this paper, the method is carried through using an uncomplicated definition in terms of the numbers of signed occurrences of variables. We demonstrate its ability to combine with previous techniques (locally extremal solutions) and make new ones practical (the systematic unbalancing of signs in formulae), resulting in a significant drop of the upper bound to 4.506. We also hint at its versatility in applying to other problems, such as the colourability of random graphs. (This is the full version of a preliminary short paper which appeared in the Proceedings of the Eleventh ACM-SIAM Symposium on Discrete Algorithms, pages 124-126, San Francisco, California, January 2000.)