Изменения
Нет описания правки
Очевидно, класс <tex>\mbox{BPP} \in \mbox{PP}</tex>.
Также существуют два [[Класс BPP|эквивалентных]] определения <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> - полином.
