How does it possible that $ZPP=RP\cap coRP$ ?
After all, it must be that $RP\cap coRP = \emptyset$
Where Am I wrong ?

  • $\begingroup$ What makes you think that their intersection is empty? $\endgroup$
    – rus9384
    Commented Aug 24, 2017 at 22:45

1 Answer 1


The complexity class P is obviously contained in their intersection (since the probability to err on either side is zero), so the intersection isn't empty.

(The complement of a complexity class isn't the same as the complement of a specific language.)


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.