Класс сложности PP (Probability Polynomial-time) состоит из всех языков L, для которых существует полиномиальная вероятностная машина Тьюринга M, такая что:

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

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

Можно показать, что класс PP, можно определить с «чуть пониженными» требованиями к распознающей ВМТ M:

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

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

или

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

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

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

G NP NP PP PP NP->PP in coNP coNP coNP->PP in ZPP ZPP BPP BPP ZPP->BPP in RP RP ZPP->RP in coRP coRP ZPP->coRP in BPP->PP in PSPACE PSPACE PP->PSPACE in NEXP NEXP PP->NEXP in RP->NP in RP->BPP in coRP->coNP in coRP->BPP in


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