Изменения
Новая страница: «==Определение класса PP== Классом <tex>\mbox{PP}</tex> называется множество языков, для которых сущес…»
==Определение класса PP==
Классом <tex>\mbox{PP}</tex> называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее результат совпадает с принадлежностью входа данным языкам и время ее работы ограничено полиномом от длины входа.
<tex>\mbox{PP} = \{L \mid \exists m: \mbox{P}(m(x) = \[ x \in L\])\g \frac{1}{2}\}</tex>
В этом определениях <tex>m</tex> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]], время работы которой ограничено полиномом от длины входа.
==Определение класса BPP==
Классом <tex>\mbox{PP}</tex> называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее результат совпадает с принадлежностью входа данным языкам и время ее работы ограничено полиномом от длины входа.
<tex>\mbox{PP} = \{L \mid \exists m: \mbox{P}(m(x) = \[ x \in L\])\g \frac{1}{2}\}</tex>
В этом определениях <tex>m</tex> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]], время работы которой ограничено полиномом от длины входа.
==Определение класса BPP==
