Изменения

Классом <tex>\mbox{PP}</tex> (от англ. ''probabilistic, polynomial'')называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее выходное значение совпадает с принадлежностью входа данным языкам больше <tex>\frac{1}{2}</tex> и время ее работы ограничено полиномом от длины входа.

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