The classes RP, coRP, ZPP, BPP, and PP

Let $L$ be a language. Each bounded-error class below is defined by the existence of a probabilistic polynomial-time machine $M$ satisfying the stated conditions on every input $x$.

• $L$ lies in RP when there exists such an $M$ for which:

  • if $x\mathrm{\notin }L$, then $M$ rejects with probability $1$;
  • if $x\in L$, then $M$ accepts with probability at least $1\mathrm{/}2$.

• $L$ lies in coRP when there exists such an $M$ for which:

  • if $x\in L$, then $M$ accepts with probability $1$;
  • if $x\mathrm{\notin }L$, then $M$ rejects with probability at least $1\mathrm{/}2$.

• $L$ lies in BPP when there exists such an $M$ for which:

  • if $x\in L$, then $M$ accepts with probability at least $2\mathrm{/}3$;
  • if $x\mathrm{\notin }L$, then $M$ rejects with probability at least $2\mathrm{/}3$.

• $L$ lies in PP when there exists such an $M$ for which:

  • if $x\in L$, then $M$ accepts with probability strictly greater than $1\mathrm{/}2$;
  • if $x\mathrm{\notin }L$, then $M$ accepts with probability at most $1\mathrm{/}2$.

• $L$ lies in ZPP when there is a probabilistic algorithm that always outputs the correct yes/no answer and whose expected runtime is polynomial in the input length.

• The constants $1\mathrm{/}2$ and $2\mathrm{/}3$ are conventions; amplification later shows that the exact BPP error constant is inessential as long as it is bounded away from $1\mathrm{/}2$.
• The PP definition does not require any fixed gap above $1\mathrm{/}2$.