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

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