Class Description

coRP: Complement of RP

Defined in [Gil77]. (This paper does not actually discuss coRP, other than implicitly mentioning that ZPP = RP ∩ co-RP. Is there a better reference?)

Contains the problem of testing whether an integer is prime [SS77].

Linked From

BC=P: Bounded-Error C=P

The class of decision problems solvable by an NP machine such that

  1. If the answer is 'yes' then exactly 1/2 of the computation paths accept.
  2. If the answer is 'no' then either at most 1/4 or at least 3/4 of the computation paths accept.

(Here all computation paths have the same length.)

Defined in [Wat15], where it was shown that BC=P admits efficient amplification and is closed under union, intersection, disjunction, and conjunction, and that coRP ⊆ BC=P ⊆ BPP.

More about...


RP: Randomized Polynomial-Time

The class of decision problems solvable by an NP machine such that

  1. If the answer is 'yes,' at least 1/2 of computation paths accept.
  2. If the answer is 'no,' all computation paths reject.

Defined in [Gil77] (implicitly: the class VPP that is defined is equivalent to RP by running the recognizer as many times as necessary to reach probability 1/2).

Contains the problem of testing whether an integer is prime [AH87], although this problem was subsequently shown to be in P [AKS02].

For other problems in RP, see the standard text on randomized algorithms, [MR95].

Has the same p-measure as ZPP. Moreover, this measure is either zero or one. If the measure is non-zero, then ZPP = BPP = EXP [IM03].

See also: coRP, ZPP, BPP.

More about...


ZPP: Zero-Error Probabilistic Polynomial-Time

Defined as RPcoRP.

Defined as the class of problems solvable by randomized algorithms that always return the correct answer, and whose expected running time (on any input) is polynomial, in [Gil77]. (Proposition 5.5(iii) in this paper shows that the two definitions above are equivalent.)

Contains the problem of testing whether an integer is prime [SS77] [AH87].

In contrast to BPP and RP, it is not known whether showing ZPP = P requires proving superpolynomial circuit lower bounds [KI02].

There exists an oracle relative to which ZPP = EXP [Hel84a], [Hel84b], [Kur85], [Hel86].

Has the same p-measure as RP. Moreover, this measure is either zero or one. If the measure is non-zero, then ZPP = BPP = EXP [IM03].

More about...