Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-007 | 15th January 2003 00:00

Typical random 3-SAT formulae and the satisfiability threshold


Authors: Olivier Dubois, Yacine Boufkhad, Jacques Mandler
Publication: 28th January 2003 13:36
Downloads: 3343


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

ISSN 1433-8092 | Imprint