RP (complexity)

In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: In other words, the algorithm is allowed to flip a truly random coin while it is running.

[1] In this sense, if a source of random numbers is available, most algorithms in RP are highly practical.

The class BPP describes algorithms that can give incorrect answers on both YES and NO instances, and thus contains both RP and co-RP.

However, if the commonly believed conjecture P = BPP is true, then RP, co-RP, and P collapse (are all equal).

An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic Turing machines where the machine accepts if and only if at least some constant fraction of the computation paths, independent of the input size, accept.

Diagram of randomised complexity classes
RP in relation to other probabilistic complexity classes ( ZPP , co-RP, BPP , BQP , PP ), which generalise P within PSPACE . It is unknown if any of these containments are strict.