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