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

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.