ZPP

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

\({\cal ZPP}={\cal RP} \cap co{\cal RP}\)

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

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

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

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

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

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


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

Graph image creation requires permission to upload.


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