Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 124 / 1

This is Ladner's theorem. Assume $\mathbf{P}\ne \mathbf{NP}$ and let $S$ be the Boolean satisfiability problem. Enumerate all clocked polynomial-time deterministic machines as $D_0,D_1,\dots$ and all clocked polynomial-time candidate reductions as $R_0,R_1,\dots$. A standard delayed-diagonalization schedule gives a nondecreasing, unbounded, polynomial-time computable function $s:\mathbb{N}\to \mathbb{N}$ that increases only by one. DefineThe schedule alternates two requirements. At even stage $2j$, it holds $s$ fixed while searching successively larger finite sets of strings for an $x$ on which $D_j(x)$ disagrees with membership in $L$; after finding one it increments $s$. At odd stage $2j+1$, it searches for an $x$ such thatand then increments $s$. Length and simulation budgets are increased slowly enough that each finite search is eventually exhaustive but computing $s(n)$ still takes polynomial time. This is achieved, for example, by permitting only $n$ simulation steps and searches on strings of logarithmic length before deciding $s(n+1)$.

Every stage must finish. If an even stage $2j$ remained forever, then $s$ would eventually be a fixed even number, so $L$ and $S$ would differ on only finitely many strings. If $D_j$ decided $L$, those finitely many exceptions could be hardwired to decide $S$ in P, contradicting $\mathbf{P}\ne \mathbf{NP}$. If an odd stage $2j+1$ remained forever, then $s$ would eventually be odd and $L$ would be finite. A correct polynomial-time many-one reduction $R_j$ from $S$ to $L$ would again put $S$ in P. Thus every $D_j$ fails to decide $L$, and every $R_j$ fails to reduce $S$ to $L$.

Finally, $L\in \mathbf{NP}$: compute $s(|x|)$ and, when it is even, use the usual polynomial-time certificate for satisfiability. Hence

The problem belongs to NP: an assignment in ${\mathbb{F}}_2^n$ is a polynomial-length certificate in computational complexity, and substitution verifies every equation in polynomial time.

For NP-hardness, reduce the Circuit satisfiability problem. Introduce one variable in ${\mathbb{F}}_2$ for every wire of a Boolean circuit. A logical negation gate $w=\neg u$ is enforced by $w=1-u$, and a logical conjunction gate $w=u\wedge v$ is enforced by $w=uv$. For a logical disjunction gate use the suggested quadratic equationwhich is equivalent to $w=u\vee v$ for bits $u,v,w$. Add the linear equation $w_{\mathrm{out}}=1$ for the designated output wire.

The construction introduces one variable and one equation per wire or gate, so it is a polynomial-time many-one reduction. A satisfying circuit input extends uniquely through its gates to a solution of the equations, and any solution gives a consistent accepting circuit computation. Since circuit satisfiability is NP-complete, quadratic-equation satisfiability over F2 is therefore