Editing RP (complexity) (section)

== Related complexity classes ==
[[File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25|RP in relation to other probabilistic complexity classes ([[ZPP (complexity)|ZPP]], co-RP, [[BPP (complexity)|BPP]], [[BQP]], [[PP (complexity)|PP]]), which generalise [[P (complexity)|P]] within [[PSPACE]]. It is unknown if any of these containments are strict.]]
The definition of '''RP''' says that a YES-answer is always right and that a NO-answer might be wrong, as a YES-instance can return a NO-answer. The complexity class '''co-RP''' is the complement, where a YES-answer might be wrong while a NO-answer is always right.

The class '''[[Bounded-error probabilistic polynomial|BPP]]''' describes algorithms that can give incorrect answers on both YES and NO instances, and thus contains both '''RP''' and '''co-RP'''. The intersection of the sets '''RP''' and '''co-RP''' is called '''[[ZPP (complexity)|ZPP]]'''.  Just as '''RP''' may be called '''R''', some authors use the name '''co-R''' rather than '''co-RP'''.