Encyclopedia > RP

  Article Content

RP

This article is about complexity theory. For the pronunciation system, see Received Pronunciation.


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. It 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/sn. 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.

Given an integer n, the problem "is n prime?" is in Co-RP. Therefore the problem "is n composite?" is in RP.

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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Digital Rights Management

... for a clear discussion of two prominent proposals. Examples of existing "digital rights management" and "copy protection" systems: Serial copy management ...

 
 
 
This page was created in 26.8 ms