I am trying to prove the theorem that ZPP = RP $\; \cap \; co-RP$. If $L \in \; \subseteq RP \; \cap \; co-RP$ then I can see that it belongs to $ZPP$. But I am unable to prove the reverse direction, as definitions of $RP$ and $co-RP$ don't include Turing machines whose expected running time is polynomial, but $ZPP$'s definition does. Am I missing something ? How should I proceed ?

  • $\begingroup$ What can you say about the probability your Las Vegas algorithm runs more than twice its expected running time? $\endgroup$
    – Louis
    Mar 22, 2016 at 13:27

1 Answer 1


The solution is given in the link provided by you in wikipedia article ZPP. See the section Intersection Definition in the link. You need to know about Markov's Inequality though.

Markov's inequality is $P[ X \geq a] \leq E[X]/a$ if $X \geq 0$. If we substitude $a = 2E[X]$ then we will have $P[ X \geq 2 E[X]] \leq 1/2$.

So, basically we run the algorithm that witnesses $L \in \textrm{ZPP}$ for at least double its expected running time. If it gives an answer, then we give that answer. If it doesn't give any answer before we stop it, we give NO answer. The probability of incorrect NO answer is $\leq 1/2$. This polynomial time algorithm proves $L \in \textrm{RP}$.

If we give answer YES on forced stoppage then that algorithm proves $L \in \textrm{co-RP}$. Thus $\textrm{ZPP} \subseteq \textrm{RP} \cap \textrm{co-RP}$.

For the sake of completeness, I also give the proof of $\textrm{RP} \cap \textrm{co-RP}\subseteq\textrm{ZPP}$.

Suppose we have a language $L \in \textrm{RP} \cap \textrm{co-RP}$. Then $L$ has a polynomial time algorithm $A$ that answers YES at least 1/2 times for $x \in L$ and a polynomial time algorithm $B$ that answers NO at least 1/2 times for $x \not\in L$. In one iteration we do the following: Given an input $x$ in $L$, we run $A$ on $x$. If it returns YES, the answer must be YES, so we return YES. Otherwise, we are in doubt so we run $B$ on the input. If it returns NO, the answer must be NO, so we return NO. If neither occurs, we repeat this iteration. We can show that the expected running time of this algorithm is still polynomial. Thus $\textrm{RP} \cap \textrm{co-RP}\subseteq\textrm{ZPP}$.

  • $\begingroup$ Can we change the give no answer branches in the ZPP machine to accept or reject, repectively, to show that L in RP and coRP? $\endgroup$
    – Macrophage
    Dec 4, 2020 at 0:01
  • $\begingroup$ @Macrophage, firstly, I was using the first definition of ZPP, and secondly, in second definition you will need to bound incorrect yes answers with less than 1/2 probability. So, there too you may have to run the algorithm multiple times. $\endgroup$ Jan 30, 2021 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.