RP (complexity)

This article relates to theory or computation. For alternate uses, see RP (disambiguation).

In complexity theory, RP ("randomized polynomial time") is the set of problems for which a probabilistic Turing machine exists with these properties:

• It always runs in polynomial time
• If the correct answer is NO, it always returns NO
• If the correct answer is YES, then it returns YES with probability at least 1/2

In other words, the algorithm is allowed to flip a truly-random coin while it's running. If it returns YES, then the correct answer is definitely YES. If it returns NO, then the correct answer is probably NO, but it might be wrong.

If the algorithm is run n times and returns a NO every time, then the correct answer is NO with a probability of at least 1/2ⁿ. If the algorithm is run 100 times, then the chance of it giving the wrong answer every time is lower than the chance that cosmic rays corrupted the memory of the computer running the algorithm.

The fraction 1/2 in the definition is arbitrary. The set RP will contain exactly the same problems, even if the 1/2 is replaced by any nonzero probability.

The definition of RP says YES is always right and NO is usually right. The complexity class Co-RP is identical, except that NO is always right and YES is usually right. The intersection of the sets RP and Co-RP is called ZPP. Some authors use the names R and Co-R rather than RP and Co-RP.

P is a subset of RP, which is a subset of NP. Similarly, P is a subset of Co-RP which is a subset of Co-NP. It is not known whether any of these subsets are strict. It is also not known whether RP = Co-RP. It is also not known whether RP is a subset of the intersection of NP and Co-NP.

The definition of RP is based on probabilistic Turing machines. Other complexity classes based on them include BPP and ZPP. The class BQP is based on another machine with randomness: the quantum computer.