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}\)

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

Graph image creation requires permission to upload.


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