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 Aug 24 '17 at 22:45

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, privacy policy and cookie policy

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