Изменения
Нет описания правки
<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> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]].
Но это очень широкий класс, поэтому вводится класс <tex>\mbox{BPP}</tex>.
==Определение класса BPP==
<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>\mbox{BPP} \in \mbox{PP}</tex>.
Число <tex>\frac{2}{3}</tex> в определении выбрано произвольно: если вместо него выбрать любое число, строго большее <tex>\frac{1}{2}</tex>, то получится тот же самый класс. Это верно, поскольку если есть машина Тьюринга, распознающая язык с вероятностью ошибки <tex>p</tex>, то точность можно сколь угодно хорошо улучшить за счёт относительно небольшого прироста времени. Если мы запустим машину <tex>n</tex> раз подряд, а в качестве результата возьмём результат большинства запусков, то вероятность ошибки упадёт до <tex>\left(2 \sqrt{p(1-p)} \right)^n</tex>, а время станет равным <tex>O(n^{k+1})</tex>. Здесь <tex>n</tex> запусков машины рассматриваются как схема Бернулли с <tex>n</tex> испытаниями и вероятностью успеха ''1-p'', а формула, выражающая ошибку, — вероятность неудачи не менее чем в половине случаев. Если теперь запустить машину <tex>n^{2}</tex> раз подряд, то время возрастёт до <tex>O(n^{k+2})</tex>, а вероятность ошибки упадёт до <tex>\left(2 \sqrt{p(1-p)} \right)^{n^2}</tex>. Таким образом, с ростом показателя многочлена, оценивающего время, точность растёт экспоненциально, и можно достичь любого нужного значения.
