RP and ZPP

Not every coin-flipping algorithm makes the same kind of mistake. RP and ZPP are two careful refinements of the random-algorithm idea, distinguished by exactly how, and whether, they are ever allowed to lie. Think of two kinds of detective: one who never falsely accuses an innocent person but sometimes lets a guilty one walk free (one-sided error), and one who never makes a mistake at all but cannot promise exactly how long the investigation will take (zero error, random time).

RP (randomized polynomial time) is the one-sided detective. If the true answer is no, an RP algorithm always says no; if the true answer is yes, it says yes with probability at least 1/2 (and might wrongly say no). So a 'yes' from an RP algorithm is gospel — there really is a witness it found — while a 'no' might be a miss you can re-test. ZPP (zero-error probabilistic polynomial time) is the never-wrong detective: it always returns the correct answer, but its running time is random, with polynomial time only on average. These are the 'Las Vegas' algorithms (always correct, gamble on time) as opposed to the 'Monte Carlo' ones (fixed time, gamble on correctness).

The relationships are clean and worth remembering. ZPP equals RP intersect co-RP: a problem has a never-wrong, expected-polynomial algorithm exactly when both it and its complement have one-sided-error algorithms — you run both until one says yes for certain. And RP sits inside BPP, since one-sided error is a special case of bounded two-sided error. P is inside all of them. As with BPP, whether any of these classes is strictly larger than P is open, and the prevailing belief — via derandomization — is that they all collapse down to P.