Zero-error Probabilistic Polynomial Time (ZPP)

A language $L$ is said to be solvable in Zero-error Probabilistic Polynomial Time (ZPP) if there is some machine $M$ that is:

• Sound: $\text{if }w\notin L\text{ then Prob}(M(w)=1)=0$
• Complete: $\text{if }w\in L\text{ then Prob}(M(w)=1)=1$
• Expected Polynomial-time: $E[T(n)]\in O(n^k)\text{ for some }k>0$

This class corresponds to Las Vegas Algorithms, these are randomised algorithms that are always sound and complete, but their runtime may vary due to their probabilistic nature.

Always correct and probably fast.