Zero-error probabilistic polynomial-time

The class of decision problems decided by a probabilistic polynomial-time algorithm that never outputs a wrong answer and outputs ”?” with probability at most 1/2 on every input; equivalently, by a zero-error algorithm with expected polynomial running time — Gil77. Equivalently,

$$\mathbf{ZPP}=\mathbf{RP}\cap \mathbf{coRP}.$$

For $L\in \mathbf{RP}\cap \mathbf{coRP}$, take an RP machine $M_1$ for $L$ and an RP machine $M_0$ for its complement (each accepts every instance in its language with probability at least 1/2 and accepts no instance outside it), and run both on input $x$: output “yes” if $M_1$ accepts, “no” if $M_0$ accepts, and ”?” otherwise. Every non-”?” answer is correct and ”?” occurs with probability at most 1/2, so this is a Las Vegas algorithm for $L$ — Gil77.

See the complexity zoo entry here.

Known relationships

• $\mathbf{P}\subseteq \mathbf{ZPP}\subseteq \mathbf{RP}\subseteq \mathbf{BPP}$.
• If $\mathbf{P}=\mathbf{BPP}$ (the derandomization hypothesis), then $\mathbf{P}=\mathbf{ZPP}=\mathbf{RP}=\mathbf{BPP}$.
• ZPP is closed under complement: $\mathbf{ZPP}=\mathbf{coZPP}$.

Participates in

Builds on Zero-error probabilistic polynomial-time

• ZPP ⊆ RP

Produces Zero-error probabilistic polynomial-time

• P ⊆ ZPP