We assume that the language L belongs to the class RP ("randomized polynomial class" - random polynomial), if it is allowed by a probabilistic Turing machine M , for which the following conditions are satisfied:
- If w does not belong to L, then the probability that M admits w is 0.
- If w belongs to L, then the probability that M admits w is at least ½.
- There exists a polynomial p (n) for which, if w has length n, then the computations of M stop after no more than p (n) steps (regardless of the contents of a random tape).
Note. An RP class definition uses two concepts that are not related:
- Paragraphs 1 and 2 define a randomized Turing machine called a Monte Carlo type machine .
- Paragraph 3 refers to the operating time, which does not depend on whether this Turing machine is a Monte Carlo type machine.
Note. The choice of ½ as a threshold in this case is optional and this constant can be replaced by another (0 < <1). Moreover, the RP will contain the same tasks, but the languages defined by specific randomized Turing machines will change.
Adjacent difficulty classes
If the Turing machine M answers “Yes”, then this is guaranteed to be true, while “No” is true only in some cases. The co-RP complexity class is defined similarly, with the only difference being that the answer “No” is a guaranteed truth, and “Yes” is not always. The BPP class describes algorithms that can give the wrong answer in both cases. The class that is the intersection of RP and co-RP is called ZPP .
Relationship with P and NP
The class P is a subset of the class RP, which, in turn, is a subset of the class NP . In particular, P is a subset of Co-RP , which is a subset of Co-NP . However, it is not known exactly whether these inclusions are strict. Most researchers are inclined to the version that P ≠ RP or RP ≠ NP , otherwise P = NP (most scientists are inclined to believe that this is not true). It is also unknown whether RP = Co-RP is true, and whether RP is a subset of the intersection of NP and Co-NP .
A striking example of a problem that lies in Co-RP , but it is not known whether it lies in P, is the problem of : to determine whether an expression with several integer variables is polynomial identically zero. For example, x · x - y · y - ( x + y ) · ( x - y ) is the identity zero, while x · x + y · y is not.