Zero-error probabilistic polynomial-time

The class of decision problems solvable by a probabilistic polynomial-time algorithm that always outputs the correct answer but may occasionally output ”?” (i.e., a Las Vegas algorithm with expected polynomial running time). Equivalently,

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

A machine for a ZPP problem accepts all “yes” instances with probability at least 1/2 and accepts no “no” instances (RP condition), and also rejects all “no” instances with probability at least 1/2 and rejects no “yes” instances (coRP condition). Running both machines and taking the definitive answer whenever one gives a non-”?” response yields an always-correct Las Vegas algorithm.

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}$.