Изменения

Классом <tex>\mbox{PP}</tex> называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее результат совпадает с принадлежностью входа данным языкам больше <tex>\frac{1}{2}</tex> и время ее работы ограничено полиномом от длины входа.<tex>ZPP^\mbox{'PP} = \{ L | \exists m : L\mbox{T}(m)=L, T(m(x)) \le = poly(|x|) p(m(x) = ?) , \le \fracmbox{1P}{2} \}</tex>.<tex>PP = \{L | \exists m : P(m(x) = [x \in L]) \g geq \frac{1}{2} \}</tex>В этом определениях <tex>m</tex> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]], время работы которой ограничено полиномом от длины входа.

Классом <tex>\mbox{BPP}</tex> называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее результат совпадает с принадлежностью входа данным языкам больше <tex>\frac{1}{2}</tex> и время ее работы ограничено полиномом от длины входа.<tex>\mbox{BPP } = \{L |{ }\exist exists m: \mbox{T}(m,x) = Polypoly(|x|) , \and mbox{P}(m(x) = [x \in L]) > \geq \frac{2/}{3 } \}</tex><br>, где <tex>m</tex> -- [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]].<br>