[proofplan]
We start with an arbitrary language $L \in RP$ and choose a randomized polynomial-time machine deciding it with one-sided error. The random string used by this machine will serve as the nondeterministic certificate for an $NP$ verifier. Soundness follows because an $RP$ machine never accepts strings outside the language, and completeness follows because for strings inside the language at least one accepting random string exists.
[/proofplan]
[step:Choose a polynomial-time randomized machine for $L$]
Let $L \subseteq \{0,1\}^*$ be a language with $L \in RP$. By the definition of $RP$, there exist a deterministic polynomial $p: \mathbb{N} \to \mathbb{N}$ and a deterministic Turing machine $M$ such that, on input $x \in \{0,1\}^*$ and random tape $r \in \{0,1\}^{p(|x|)}$, the computation $M(x;r)$ halts in time at most $p(|x|)$ and satisfies the one-sided error conditions
\begin{align*}
x \notin L \implies \mathbb{P}_{r \in \{0,1\}^{p(|x|)}}[M(x;r) \text{ accepts}] = 0.
\end{align*}
\begin{align*}
x \in L \implies \mathbb{P}_{r \in \{0,1\}^{p(|x|)}}[M(x;r) \text{ accepts}] \geq \frac{1}{2}.
\end{align*}
Here the probability is with respect to the uniform distribution on the finite set $\{0,1\}^{p(|x|)}$. If the original $RP$ machine uses at most $p(|x|)$ random bits, we pad the random tape with unused bits so that every certificate has exactly length $p(|x|)$.
[/step]
[step:Build an $NP$ verifier using the random tape as the certificate]
Define a deterministic verifier
\begin{align*}
V: \{0,1\}^* \times \{0,1\}^* \to \{\text{accept}, \text{reject}\}
\end{align*}
as follows. On input pair $(x,c)$, where $x \in \{0,1\}^*$ is the instance and $c \in \{0,1\}^*$ is the proposed certificate, the verifier first checks whether $|c| = p(|x|)$. If not, it rejects. If $|c| = p(|x|)$, it simulates the deterministic computation $M(x;c)$ and accepts exactly when that computation accepts.
The length check takes time polynomial in $|x|+|c|$, and when $|c| = p(|x|)$ the simulation of $M(x;c)$ takes time at most $p(|x|)$. Hence $V$ is a deterministic polynomial-time verifier, and its accepted certificates have polynomial length.
[guided]
The role of the certificate is to reveal the random choices that make the randomized machine accept. Since $M$ is randomized only through its random tape, once a string $c \in \{0,1\}^{p(|x|)}$ is fixed, the computation $M(x;c)$ is completely deterministic.
We therefore define
\begin{align*}
V: \{0,1\}^* \times \{0,1\}^* \to \{\text{accept}, \text{reject}\}
\end{align*}
by making $V(x,c)$ simulate $M$ on input $x$ with random tape $c$. The verifier first checks that $|c| = p(|x|)$, because only strings of that length represent valid random tapes for the chosen machine. If the length is wrong, $V$ rejects. If the length is correct, $V$ runs the deterministic computation $M(x;c)$ and accepts precisely when $M(x;c)$ accepts.
This verifier is polynomial time. The length check is polynomial in the input size to the verifier. When $|c| = p(|x|)$, the simulation time is at most $p(|x|)$ by the chosen runtime bound for $M$. Since $p$ is a polynomial, the certificate length $p(|x|)$ is also polynomial in $|x|$. Thus $V$ has exactly the form required of an $NP$ verifier: deterministic polynomial-time computation with polynomial-length certificates.
[/guided]
[/step]
[step:Verify soundness for strings outside $L$]
Let $x \in \{0,1\}^*$ satisfy $x \notin L$. By the $RP$ soundness condition,
\begin{align*}
\mathbb{P}_{r \in \{0,1\}^{p(|x|)}}[M(x;r) \text{ accepts}] = 0.
\end{align*}
Because the sample space $\{0,1\}^{p(|x|)}$ is finite and uniformly distributed, this means there is no string $r \in \{0,1\}^{p(|x|)}$ such that $M(x;r)$ accepts. Therefore no certificate $c \in \{0,1\}^*$ is accepted by $V$ on input $x$: certificates of the wrong length are rejected by definition, and certificates of length $p(|x|)$ are rejected because the corresponding computation of $M$ rejects. Hence
\begin{align*}
x \notin L \implies \text{there is no certificate } c \text{ with } V(x,c) \text{ accepting}.
\end{align*}
[/step]
[step:Verify completeness for strings inside $L$]
Let $x \in \{0,1\}^*$ satisfy $x \in L$. By the $RP$ completeness condition,
\begin{align*}
\mathbb{P}_{r \in \{0,1\}^{p(|x|)}}[M(x;r) \text{ accepts}] \geq \frac{1}{2}.
\end{align*}
Since the finite set $\{0,1\}^{p(|x|)}$ is nonempty, this positive probability implies that at least one string $r_0 \in \{0,1\}^{p(|x|)}$ satisfies that $M(x;r_0)$ accepts. Taking $c = r_0$ as the certificate, the verifier $V$ passes the length check and accepts because it simulates the accepting computation $M(x;r_0)$. Therefore
\begin{align*}
x \in L \implies \text{there exists a certificate } c \text{ with } V(x,c) \text{ accepting}.
\end{align*}
[/step]
[step:Conclude that $L$ belongs to $NP$]
The verifier $V$ is deterministic polynomial time, uses certificates of length at most $p(|x|)$, rejects every input outside $L$ for every certificate, and accepts every input inside $L$ for at least one certificate. Hence $V$ is an $NP$ verifier for $L$, so $L \in NP$.
Since $L \in RP$ was arbitrary, every language in $RP$ belongs to $NP$. Therefore $RP \subseteq NP$.
[/step]
