I think I understand the RP complexity class (along with coRP, BPP, and ZPP). However, I can't seem to think of how an RP algorithm might be formulated.

How can the random coin flip possibilities allow for a guaranteed response of NO when the correct answer is NO, yet return with a probabilistic chance YES or NO when the answer is YES?

Are these actually algorithms we have examples of or is it just a theoretical class without any known examples? If there are examples, could someone please lay one out?

  • 1
    $\begingroup$ I think the random coin flip only applies for the "Yes" response in your example. The algorithm may perform normally in its deciding processes. $\endgroup$
    – d'alar'cop
    Jun 3 '14 at 2:01
  • 2
    $\begingroup$ What reading and research have you done? Standard textbooks on randomized algorithms typically contain some discussion of this and example algorithms. Have you tried looking through textbooks for examples of this sort of thing? $\endgroup$
    – D.W.
    Jun 3 '14 at 6:33
  • $\begingroup$ @D.W. : I was reading Computational Complexity: A Modern Approach by Arora and Barak. Maybe I've missed something but I didn't see any such examples in the chapter where RP, coRP, and ZPP are defined. At least, not until the chapter "Notes and history" at the end of the chapter which I have now read. $\endgroup$ Jun 5 '14 at 21:07

The algorithms you are looking for are also called one-sided-error Monte Carlo algorithms.

The idea is to randomly guess a witness for the input being a YES-instance. If you find one, your answer "YES" is always correct; if you don't find one, you say "NO" even though the correct answer may be "YES" (we want to restrict the likelihood of this event). If the input is a NO-instance we can never find such a witness, so we always output NO correctly.

One well-known example is the Solovay–Strassen primality test.

  • $\begingroup$ I Solovay-Strassen still popular? I thought it had completely lost out to Miller-Rabin. $\endgroup$
    – user12859
    Jun 3 '14 at 2:03
  • $\begingroup$ @RickyDemer: I understand "popular" to mean "widely known", which not the same thing at all as "widely used". I think Miller-Rabin is also an example for this class of algorithms, though. $\endgroup$
    – Raphael
    Jun 3 '14 at 2:03

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.