= Solution
First suppose $L\in\mathbf{RP}\cap\mathbf{co\text{-}RP}$. Run the RP algorithm for $L$ and the RP algorithm for its complement with fresh random bits. If the first accepts, output one; if the second accepts, output zero; otherwise repeat. Neither output can be wrong, and on every input the appropriate algorithm accepts in each round with probability at least $1/2$. The number of rounds is dominated by a <geometric distribution> of mean two, so this is an always-correct algorithm with polynomial <expected value>[expected running time].
Conversely, let $T$ be always correct when it halts and have expected running time at most $p(n)$. Run it for $2p(n)$ steps. <Markov inequality> gives
$$
\mathbb P(T\text{ has not halted by }2p(n))\leq\frac12.
$$
Accept exactly when $T$ halts and outputs one; this is an RP algorithm for $L$. Accepting exactly when it halts and outputs zero is an RP algorithm for the complement. Therefore
$$
\boxed{\mathbf{ZPP}=\mathbf{RP}\cap\mathbf{co\text{-}RP}}
$$
is equivalent to zero-error expected polynomial time.
Back to article page
