= Solution
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 most
$$
2^n2^{-(n+1)}=\frac12.
$$
Thus 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
$$
\boxed{\mathbf{RP}\subseteq\mathbf P/\mathrm{poly}.}
$$
Back to article page
