# Monte Carlo Algorithms : Are there any problems where two opposite Monte Carlo algorithms could solve it?

I started reading on Probabilistic algorithms and Monte-Carlo algorithms. Since a Monte-Carlo can only give a certain answer for either True or False, I was wondering if it's conceivable that for the same problem, there exist two opposite Monte-Carlo Algorithms capable of giving a certain answer. (By opposite, I mean one would be sure when it's FALSE, and the other would be certain when it's TRUE)

For example : There exist a prime number test Monte-Carlo based algorithm that can check whether or not a number "n" is prime. If the answer is FALSE, then "n" is not a prime number (it is a composed number). However, if the answer were to be TRUE, then "n" COULD be prime (with a certain probability). To my knowledge, there is no efficient algorithm (Monte-Carlo) capable of saying with certainty if "n" is a prime number.

• Such problems correspond to Las Vegas algorithm, as expressed by the identity $\mathsf{ZPP}=\mathsf{RP} \cap \mathsf{coRP}$. See for example the Wikipedia page on ZPP. Dec 1, 2018 at 23:50
• Your example is a bit problematic, since primality can be tested in deterministic polynomial time. Dec 1, 2018 at 23:50

In the language of complexity theory, this corresponds to the statement $$\mathsf{ZPP} = \mathsf{RP} \cap \mathsf{coRP}$$. You can find more information on $$\mathsf{ZPP}$$ on Wikipedia.