Класс сложности ZPP (Zero-Probability Polynomial-time) можно определить, как пересечение классов RP и coRP:

Z P P = R P c o R P {\cal ZPP}={\cal RP} \cap co{\cal RP}

или, через самостоятельное определение:

Класс сложности ZPP состоит из всех языков L, для которых существует полиномиальная вероятностная машина Тьюринга M, возвращающая только ответы «0», «1», «не знаю», причем::

x L P [ M ( x ) = 1 ] > 1 2 x \in L \Rightarrow P[M(x)=1] > \frac{1}{2}

P [ M ( x ) = 1 ] + P [ M ( x ) = ] = 1 P[M(x)=1]+P[M(x)=\mbox{}]=1

x L P [ M ( x ) = 0 ] > 1 2 x \notin L \Rightarrow P[M(x)=0] > \frac{1}{2}

P [ M ( x ) = 0 ] + P [ M ( x ) = ] = 1 P[M(x)=0]+P[M(x)=\mbox{}]=1


Диаграмма «ближайших» классов

G P P ZPP ZPP P->ZPP in NP NP PP PP NP->PP in coNP coNP coNP->PP in BPP BPP ZPP->BPP in RP RP ZPP->RP in coRP coRP ZPP->coRP in BPP->PP in RP->NP in RP->BPP in coRP->coNP in coRP->BPP in


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.