Submit progress

on Satisfiability threshold for random 3-SAT ($C_{52}$)

The statement

Let $m,n$ be positive integers and let $V$ be a set of $n$ Boolean variables. By a random formula of density $r = m/n$ , we mean a collection of $m$ clauses selected u.a.r. with replacement from the set of $8\binom{n}{3}$ clauses on three distinct variables from $V$ . For linguistic convenience, formulas with variables from $V$ will be called $n$ -formulas.

It is conjectured, and corroborated by experimental results (see e.g. [LT1992]) and non-rigorous considerations of Statistical Physics (see e.g. [MZ1997]), that there is a constant $r_3 \approx 4.2$ , here to be denoted also by $C_{52}$ , such that for any constant $r$

\text{if } r > r_3, \text{ then } \lim_{n \to \infty}\Pr\!\left[\text{an } n\text{-formula with density } r \text{ is satisfiable}\right]= 0,

whereas

\text{if } r < r_3, \text{ then } \lim_{n \to \infty}\Pr\!\left[\text{an } n\text{-formula with density } r \text{ is satisfiable}\right] = 1.

It has been proved by Friedgut [F1999] that there is a sequence $r_{3,n}, n = 1, \dots$ such that for any $\epsilon > 0$

\lim_{n \to \infty}\Pr\!\left[\text{an } n\text{-formula with density } \ge (r_{3,n} + \epsilon) \text{ is satisfiable}\right] = 0,

whereas

\lim_{n \to \infty}\Pr\!\left[\text{an } n\text{-formula with density } \le (r_{3,n} - \epsilon) \text{ is satisfiable}\right] = 1.

Below we give the rigorously proved upper bounds for $\limsup_{n \to \infty} r_{3,n}$ and the rigorously proved lower bounds for $\liminf_{n \to \infty} r_{3,n}$ .

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.