ZPP

Remarks

Equivalently, $\mathrm{ZPP} = \mathrm{RP} \cap \text{co-RP}$, with RP the class of one-sided error. Suppose $L$ has an RP machine $M_1$ and its complement has an RP machine $M_2$. Run both in rounds until one of them accepts. An accepting run of $M_1$ proves $x \in L$, and an accepting run of $M_2$ proves $x \notin L$. Each round succeeds with probability at least $1/2$, so the expected number of rounds is at most $2$. Conversely, by Markov's inequality a ZPP machine stopped after $2p(\abs{x})$ steps has halted with probability at least $1/2$, which gives RP machines for $L$ and its complement.

Example: every language in P is in ZPP, using a machine that ignores its coins.

Non-example: a machine that runs in polynomial time but answers wrongly with probability $1/10$ on some input fails clause 1.

Another equivalent form: there is a polynomial-time machine with outputs $0$, $1$ and "?" that never gives a wrong $0$ or $1$ and outputs "?" with probability at most $1/2$.