Random k-SAT Is Not Easy on Average: Hardness Concentrates at the Threshold — Epoche B2
Revisiting Average-Case Performance of NP-Hard Problems A familiar consolation is offered to anyone who has just learned that satisfiability, graph colouring and the travelling salesman problem are NP-hard: never mind, the hardness is only in the worst case, and real instances are easy on average. Modern SAT solvers do settle industrial formulas with millions of variables, so the consolation is not empty. But "easy on average" is a claim about a probability distribution over inputs, and until that distribution is named the claim has no content. This note takes the one family for which the distribution is named — uniformly random $k$-SAT — and asks what its "easy-hard-easy" pattern establishes. The answer inverts the folklore: hardness does not vanish under randomisation [1] , it concentrates into a narrow window whose location we can compute. What an average-case claim must specify NP-hardness is a statement with a universal quantifier over inputs: no polynomial-time algorithm decides every instance, unless P = NP. An average-case claim replaces that quantifier with an expectation [2] , and an expectation is meaningless without a measure. Writing $\mathcal{D}_n$ for a distribution over instances of size $n$ and $T(I)$ for the running time of a fixed algorithm on instance $I$, Levin's definition of tractability on average, here simplified for a fixed input size $n$, is not that the mean time is polynomial but the more permissive, composition-stable condition $$ \mathbb{E}_{I \sim \mathcal{D}_n}\!\left[\,T(I)^{1/c}\,\right] \;\le\; C\,n \qquad \text{for some constants } c,\,C \gt 0 . $$ The implication between the two runs one way only. Because $x \mapsto x^{1/c}$ is concave, Jensen's inequality gives $\mathbb{E}[T^{1/c}] \le \left(\mathbb{E}[T]\right)^{1/c}$, so polynomial expected time implies the condition above as soon as $c$ is at least the degree. The converse fails: an algorithm costing $2^{cn}$ steps on a $2^{-n}$ fraction of inputs and $O(1)$ steps otherwise satisfies it, yet has mean time $2^{(c-1)n}$. Levin's class therefore strictly contains expected-polynomial-time. It is the preferred definition not because it demands more but because it is robust: unlike a bound on the mean, it survives polynomial changes of machine model and composition under reductions. The pair $(\text{problem},\,\mathcal{D})$, not the problem alone, is the object being classified. Change $\mathcal{D}$ and the answer changes: a distribution that plants a satisfying assignment and then samples clauses consistent with it yields formulas a simple algorithm solves in polynomial time, while the uniform distribution at the same clause density can be intractable. Neither result transfers to the other, and neither bears on the worst case. "NP-hard problems are easy on average" is therefore a family of claims, one per distribution, most of them untested. Random $k$-SAT: the model where "typical" is well defined Fix $n$ Boolean variables and draw $m$ clauses independently and uniformly at random from the $\binom{n}{k}2^{k}$ clauses containing $k$ distinct variables. The single control parameter is the clause-to-variable ratio $$ \alpha \;=\; \frac{m}{n}, $$ which measures constraint per degree of freedom: each clause forbids exactly one of the $2^{k}$ assignments to its $k$ variables, so an assignment survives a random clause with probability $1 - 2^{-k}$. Let $Z$ denote the number of satisfying assignments. Because the clauses are independent, the first moment is exact: $$ \mathbb{E}[Z] \;=\; 2^{n}\left(1-2^{-k}\right)^{m} \;=\; 2^{\,n\left[\,1 \,+\, \alpha \log_2\!\left(1-2^{-k}\right)\right]} . $$ For $k=3$ the bracket is $1 - 0.19265\,\alpha$. It is positive up to $\alpha_{\mathrm{UB}} = 5.191$ and negative beyond, and since $\Pr[Z \ge 1] \le \mathbb{E}[Z]$ by Markov's inequality, $$ \alpha \gt \alpha_{\mathrm{UB}} = \frac{-1}{\log_2\!\left(1-2^{-k}\right)} \;\implies\; \Pr\left[\,F_{n,\alpha n} \text{ satisfiable}\,\right] \to 0 . $$ This is a genuine upper bound on where satisfiable formulas can survive, and it is loose — itself the first lesson. The expectation $\mathbb{E}[Z]$ is still exponentially large at $\alpha = 5$, yet random formulas at that density are unsatisfiable with probability tending to one: the mean is dominated by a vanishing fraction of unusually solution-rich formulas, so the typical formula has far fewer solutions than the average one. An expectation and a typical realisation are different objects, and conflating them is exactly the error that "easy on average" invites. The threshold at $\alpha_c \approx 4.267$ Numerically, the transition for $k=3$ sits at $$ \lim_{n\to\infty}\Pr\left[\,F_{n,\alpha n}\text{ satisfiable}\,\right] \;=\; \begin{cases} 1, & \alpha \lt \alpha_c,\\[2pt] 0, & \alpha \gt \alpha_c,\end{cases} \qquad \alpha_c \approx 4.267 . $$ The regime of validity deserves care. Friedgut proved the transition sharp &mdash [3] ; its width shrinks to zero as $n$ grows — but convergence of the threshold sequence to a constant is still unproven for $k=3$; rigorous bounds bracket it between about $3.52$ and $4.49$, and $4.267$ comes from numerics and the non-rigorous cavity method. For large $k$ the picture is a theorem (Ding, Sly and Sun). The defensible statement: satisfiability falls from near-certain to near-impossible across a window in $\alpha$ that narrows with $n$, centred near $4.267$. Horizontal axis: clause-to-variable ratio alpha from 0 to 8. Blue curve: probability that a random 3-SAT formula is satisfiable, near 1 on the left, falling steeply at alpha = 4.267, near 0 on the right. Amber curve: median backtracking search nodes on a logarithmic scale, rising into the drop, peaking there, then decaying. 0 1 2 4 6 8 clause-to-variable ratio α = m / n α c ≈ 4.267 Pr[satisfiable] median search nodes (log scale) Fig. 1 — The random 3-SAT phase transition. The satisfiable fraction (blue) falls from near one to near zero across a window that narrows as $n$ grows; the median num