2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 1 '18 at 23:50
  • $\begingroup$ Your example is a bit problematic, since primality can be tested in deterministic polynomial time. $\endgroup$ – Yuval Filmus Dec 1 '18 at 23:50
2
$\begingroup$

A Las Vegas algorithm is one which is always correct, but is only efficient in expectation. Given two "opposite" Monte Carlo algorithm, you can create a Las Vegas algorithm by alternating both algorithms (or running them in parallel), halting whenever one of them produces a certain answer.

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.

$\endgroup$
  • $\begingroup$ Interesting link, thank you! So given enough time, the answer is sure to come out? I was under the impression that Las Vegas could be unable to answer (LV always gives the right answer, or it doesn't answer) $\endgroup$ – Robert Dec 2 '18 at 0:16
  • $\begingroup$ @Robert maybe you could consider accepting this answer? $\endgroup$ – Evil May 1 at 1:24

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.