Approximating the Unsatisfiability Threshold of Random Formulae
DANNY KRIZANC
(Wesleyan University)
Let $\phi$ be a random Boolean formula that is an instance of 3-SAT.
We consider the problem of computing the least real number $\kappa$ such
that if the ratio of the number of clauses over the number of variables
of $\phi$ strictly exceeds $\kappa$, then $\phi$ is almost certainly
unsatisfiable. By a well known and more or less straightforward argument,
it can be shown that $\kappa \leq 5.191$. This upper bound was improved by
Kamath, Motwani, Palem, and Spirakis to 4.758, by first providing new
improved
bounds for the occupancy problem. There is strong experimental evidence
that
the value of $\kappa$ is around 4.2. In this work, we define, in terms of
the random formula $\phi$, a decreasing sequence of random variables such
that
if the expected value of any one of them converges to zero, then $\phi$ is
almost certainly unsatisfiable. By letting the expected value of the first
term
of the sequence converge to zero, we obtain, by simple and elementary
computations,
an upper bound for $\kappa$ equal to 4.667. In general, by letting the
expected
value of further terms of this sequence converge to zero, one can, in
principle,
obtain even better approximations to $\kappa$. This technique generalizes
in a
straightforward manner to $k$-SAT, for $k>3$.
Joint work with Lefteris Kirousis and Evangelos Kranakis.