I think I understand the RP complexity class (along with coRP, BPP, and ZPP). Ho
ID: 651871 • Letter: I
Question
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?
Explanation / Answer
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