= Solution
Let $V(x,w)$ be a polynomial-time verifier for $f\in\mathbf{NP}$, with witnesses of length $p(|x|)$. Consider the prefix language
$$
B=\{(x,u):\text{there exists }v\text{ such that }V(x,uv)=1\}.
$$
This 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)$ satisfies
$$
\boxed{V(x,C_n(x))=1.}
$$
On negative inputs the output may be arbitrary, as required.
Back to article page
