PP

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

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

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

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

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

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

или

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

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

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

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