Section 7.2.2.2: Satisfiability

Exercise 193. [HM48] [HM48] Determine the satisfiability threshold (81) of random 3SAT. Is it true that $\lim_{n\to\infty} S_{3,n}/n = \limsup_{n\to\infty} S_{3,n}/n$? If so, is the limit $\approx 4.2667$?

Verified: no
Solve time: 2m04s

---

Setup

Let $S_{k,n}$ denote the satisfiability threshold defined in (81) of Section 7.2.2.2. In the random $k$SAT model, there are $n$ variables and clauses are chosen uniformly from the possible $k$-literal clauses. The threshold question asks for the asymptotic value of the clause density at which satisfiable instances cease to occur with high probability.

For $k=3$, the quantity of interest is therefore

$$ \frac{S_{3,n}}{n}. $$

Exercise 193 asks whether

$$ \lim_{n\to\infty}\frac{S_{3,n}}{n}

\limsup_{n\to\infty}\frac{S_{3,n}}{n} $$

and whether this limit equals approximately $4.2667$.

The first equality asks whether the normalized threshold has a genuine limit rather than merely having a subsequential upper limit. The second asks whether the conjectured numerical value from the statistical physics analysis is the true threshold.

Known results

The exact satisfiability threshold for random 3SAT is not known. The value

$$ \alpha_3\approx 4.2667 $$

comes from the cavity method of statistical physics, particularly the work of Mézard, Parisi, and Zecchina and subsequent refinements. This method gives a highly accurate prediction, but it is not a rigorous proof of the threshold value.

A sharp threshold result is known in the general probabilistic sense: the transition from satisfiable to unsatisfiable instances occurs in a narrow window as the number of clauses varies. However, this does not determine the location of the window.

For random $k$SAT, exact threshold values are known for $k=2$ and for sufficiently large $k$, where rigorous work confirms the existence of the limiting threshold density. The case $k=3$ remains one of the difficult small-$k$ cases.

The best rigorous bounds for random 3SAT have approached the conjectured value from both sides, but they do not prove equality. Earlier rigorous estimates placed the threshold below $4.506$ and above smaller constants, leaving a nonzero interval around the predicted value.

Partial argument

The numerical value $4.2667$ is obtained by considering the random 3SAT ensemble with

$$ m=\alpha n $$

clauses and analyzing the evolution of the space of satisfying assignments as $\alpha$ increases. The cavity method predicts a critical density $\alpha_3$ at which the satisfiable phase disappears:

$$ \alpha_3=4.2667\ldots . $$

This prediction agrees with extensive computational experiments, but the method does not provide a proof that

$$ \lim_{n\to\infty}\frac{S_{3,n}}{n}

4.2667\ldots . $$

A proof of the equality would require two separate rigorous statements. First, one would need to prove the existence of the limit

$$ \lim_{n\to\infty}\frac{S_{3,n}}{n}. $$

Second, one would need to prove matching upper and lower bounds converging to $4.2667\ldots$.

The lower bound problem requires proving that for every fixed $\epsilon>0$,

$$ \alpha<4.2667-\epsilon $$

implies that a random 3SAT formula with $\alpha n$ clauses is satisfiable with probability tending to $1$. The upper bound problem requires proving that

$$ \alpha>4.2667+\epsilon $$

implies that such a formula is unsatisfiable with probability tending to $1$.

Neither statement is currently available at the conjectured constant. The known rigorous techniques establish only weaker bounds separated from $4.2667\ldots$.

Consequently, the argument in Section 7.2.2.2 leading to the threshold definition (81) gives the correct framework for the question, but it does not determine the random 3SAT threshold.

Status

The problem remains open in the form posed by Knuth. The conjecture

$$ \lim_{n\to\infty}\frac{S_{3,n}}{n}

\limsup_{n\to\infty}\frac{S_{3,n}}{n}

4.2667\ldots $$

is strongly supported by statistical physics calculations and experiments, but no rigorous proof is known.

Thus the answer to the first question is not known, and the answer to the second question is also not known. The number $4.2667\ldots$ should be regarded as the predicted threshold, not as an established theorem. This is precisely the type of frontier problem for which Knuth assigns a very high difficulty rating.

∎