TR03-007 Authors: Olivier Dubois, Yacine Boufkhad, Jacques Mandler

Publication: 28th January 2003 13:36

Downloads: 1535

Keywords:

$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.)