Изменения
Нет описания правки
==Определение класса PP==
Классом <tex>\mbox{PP}</tex> (от англ. ''probabilistic, polynomial'') называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее выходное значение совпадает с принадлежностью входа данным языкам больше <tex>\frac{1}{2}</tex> и время ее работы ограничено полиномом от длины входа.
<tex>\mbox{PP} = \{L ~ | ~ \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) > \frac{1}{2} \}</tex>
В этом определениях <tex>m</tex> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]].
==Определение класса BPP==
Классом <tex>\mbox{BPP}</tex> (от англ. ''bounded-error, probabilistic, polynomial'') называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее выходное значение совпадает с принадлежностью входа данным языкам больше <tex>\frac{2}{3}</tex> и время ее работы ограничено полиномом от длины входа.
<tex>\mbox{BPP} = \{L ~ | ~ \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) > \frac{2}{3} \}</tex>
, где <tex>m</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]].
Также существуют два эквивалентных определения <tex>BPP</tex>:
*<tex>\mbox{BPP}_{weak} = \{L ~ | ~ \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) > \frac{1}{2} + 1/p(|x|)\}</tex>, где <tex>m</tex> - [[Вероятностная машина Тьюринга|ВМТ]], а <tex>p(|x|): \forall x ~ p(|x|) > 2</tex> - полином.*<tex>\mbox{BPP}_{strong} = \{L ~ | ~ \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) > 1 - 2^{-p(|x|)}\}</tex>, где <tex>m</tex> - [[Вероятностная машина Тьюринга|ВМТ]], а <tex>p(|x|)</tex> - полином.
