Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 124 (Introduction to Computational Complexity)

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

A decision problem $B$ is NL-complete when $B\in \mathbf{NL}$ and every language $A\in \mathbf{NL}$ has a deterministic logarithmic space many-one reduction to $B$.

The directed graph reachability problem is the standard example. It lies in NL because a machine stores the current vertex and a counter, nondeterministically guesses at most $|V|-1$ successive edges, and accepts upon reaching $t$; this uses $O(\log |V|)$ space. For hardness, given an NL machine $M$ and input $x$, construct its configuration graph. Its configurations have logarithmic length, adjacency can be computed in logarithmic space, andAdding one target joined from every accepting configuration gives the required logarithmic-space reduction.

It suffices to recognize non-reachability in NL, since directed reachability is NL-complete. Let $c_k$ be the number of vertices reachable from $s$ by a directed path of length at most $k$. Clearly $c_0=1$. The inductive counting argument computes and verifies $c_{k+1}$ from $c_k$ using logarithmic space.

For each vertex $v$, reachability within $k+1$ steps has an NL certificate: guess such a path. Non-reachability within $k+1$ steps can be certified relative to the trusted value $c_k$ by enumerating vertices $u$, exhibiting paths of length at most $k$ to exactly $c_k$ distinct vertices, and checking that none is $v$ or has an edge to $v$. Because there are exactly $c_k$ reachable vertices, this list cannot omit a reachable predecessor. Counters, vertex names and one guessed path need only logarithmic space. Repeating this check in a fixed vertex order and counting the positive cases produces the exact $c_{k+1}$.

After $|V|-1$ rounds, the procedure knows the number of all vertices reachable from $s$. It accepts non-reachability of $t$ after certifying, by the same complete enumeration, that $t$ is absent. Thus the complement of directed reachability belongs to NL. Since every NL language reduces to reachability and log-space reductions are closed under complementation, this proves the Immerman–Szelepcsényi theorem

Membership follows from $\mathbf{NL}=\mathbf{co}\text{-}\mathbf{NL}$. A directed graph is not strongly connected exactly when there is a pair $(u,v)$ for which $v$ is not reachable from $u$. Guessing the pair and using the NL procedure for non-reachability puts non-strong-connectivity in NL, hence strong connectivity is in co-NL and therefore in NL.

For NL-hardness, reduce directed reachability. Given $(G,s,t)$, form $G^{\prime }$ by retaining all edges of $G$, adding $v\to s$ for every vertex $v$, and adding $t\to v$ for every vertex $v$. If $t$ is reachable from $s$ in $G$, then any $u$ reaches any $v$ in $G^{\prime }$ alongConversely, if $G^{\prime }$ is strongly connected then $s$ reaches $t$. A simple $s$-to-$t$ path cannot use an added edge out of $t$ before arriving at $t$, and every added edge into $s$ merely returns the path to its starting vertex; deleting the resulting cycle leaves an $s$-to-$t$ path made from edges of $G$. The construction is computable in logarithmic space, so deciding strong connectivity is

Let $V(x,w)$ be a polynomial-time verifier for $f\in \mathbf{NP}$, with witnesses of length $p(|x|)$. Consider the prefix languageThis language lies in NP, so the assumption $\mathbf{NP}\subseteq \mathbf{P}/\mathrm{poly}$ supplies a polynomial-size circuit family deciding $B$.

Apply the usual search-to-decision reduction. Starting with the empty prefix, append zero if the circuit says that some accepting witness has that extended prefix; otherwise append one. Repeat for $p(n)$ positions. Composing the polynomially many copies of the decision circuit produces a polynomial-size circuit $C_n$. Whenever $f(x)=1$, at least one accepting extension exists at every step, so the final string $C_n(x)$ satisfiesOn negative inputs the output may be arbitrary, as required.

This is the Karp–Lipton theorem. It is enough to place ${\Pi }_2^{\mathbf{P}}$ inside ${\Sigma }_2^{\mathbf{P}}$. Let $L\in {\Pi }_2^{\mathbf{P}}$, so for a polynomial-time predicate $R$ and polynomially bounded strings,The NP search problem that receives $(x,y)$ and seeks such a $z$ has, by part (i), a polynomial-size circuit family producing a valid witness whenever one exists. For each input length there is therefore a polynomial-size circuit $C$ such that, for every relevant $x,y$, existence of a witness implies $R(x,y,C(x,y))$.

Consequentlywhere the existentially guessed circuit description has polynomial length and evaluation of $C$ is polynomial time. This is a ${\Sigma }_2^{\mathbf{P}}$ description. Hence ${\Pi }_2^{\mathbf{P}}\subseteq {\Sigma }_2^{\mathbf{P}}$; complementation gives the reverse inclusion, and merging adjacent equal quantifier blocks collapses every higher level. Thus the polynomial hierarchy satisfies

Yes. The usual collapse relativizes because every machine involved receives the same oracle $A$. Induct on the levels of the polynomial hierarchy. The hypothesis givesIf the preceding level is contained in ${\mathbf{P}}^A$, then its oracle queries can be simulated in polynomial time with oracle $A$. A nondeterministic machine for the next existential level is therefore only an ${\mathbf{NP}}^A$ machine, hence a ${\mathbf{P}}^A$ machine by hypothesis. Complements give the corresponding universal level. The induction yields

A language $L$ belongs to RP when a polynomial-time randomized algorithm rejects every $x\notin L$ and accepts every $x\in L$ with probability at least $1/2$.

Amplify the algorithm on length-$n$ inputs with $n+1$ independent repetitions, accepting if any repetition accepts. Its error on each positive input is at most $2^{-(n+1)}$, while it still never accepts a negative input. Choose all random bits for all repetitions in advance. By the union bound, the probability that this one fixed choice fails on at least one of the at most $2^n$ positive strings is at mostThus some random string works simultaneously for every input of length $n$. Hardwire that string into the polynomial-time computation and compile it into a Boolean circuit. The resulting polynomial-size circuit family decides $L$, proving

First suppose $L\in \mathbf{RP}\cap \mathbf{co}\text{-}\mathbf{RP}$. Run the RP algorithm for $L$ and the RP algorithm for its complement with fresh random bits. If the first accepts, output one; if the second accepts, output zero; otherwise repeat. Neither output can be wrong, and on every input the appropriate algorithm accepts in each round with probability at least $1/2$. The number of rounds is dominated by a geometric distribution of mean two, so this is an always-correct algorithm with polynomial expected running time.

Conversely, let $T$ be always correct when it halts and have expected running time at most $p(n)$. Run it for $2p(n)$ steps. Markov inequality givesAccept exactly when $T$ halts and outputs one; this is an RP algorithm for $L$. Accepting exactly when it halts and outputs zero is an RP algorithm for the complement. Thereforeis equivalent to zero-error expected polynomial time.

We give the Agrawal–Biswas primality test, which has one-sided error. Small inputs and perfect powers can first be recognized deterministically. For every remaining integer $n$, put $d=\lceil 4{\log }_{2}n\rceil$ and choose a uniformly random monic polynomialUsing repeated squaring in the quotient ring $(\mathbb{Z}/n\mathbb{Z})[X]/(r)$, test the identityThis takes time polynomial in $\log n$ because every intermediate polynomial has degree below $d=O(\log n)$.

If $n$ is prime, the intermediate binomial coefficients are divisible by $n$, so the identity always holds. Now suppose that $n$ is composite and is not a prime power. Choose a prime divisor $p$ and write $n=p^{a}m$ with $p\nmid m$ and $m>1$. Over ${\mathbb{F}}_p$,because an intermediate coefficient equal to $m$ is nonzero modulo $p$. Henceis a nonzero polynomial of degree below $n$ over ${\mathbb{F}}_p$.

Reduction of random $r$ modulo $p$ is uniform among the $p^d$ monic degree-$d$ polynomials. The polynomial $F$ has at most $n/d$ distinct monic irreducible factors of degree $d$. On the other hand, the number $I_p(d)$ of monic irreducibles of degree $d$ obeys the standard lower boundWhenever $r\mathrm{mod}p$ is one of these irreducibles but does not divide $F$, the tested congruence fails. Thus one trial detects compositeness with probability at leastafter the finitely many small $n$ are handled directly. Repeating $2d$ times makes the probability of missing a composite less than $(1-1/(2d){)}^{2d}<1/2$, while a prime is never rejected. Therefore compositeness is in RP, and primality testing is in