Сложностный класс BPP

Определение класса PP

Классом $\mbox{PP}$ (от англ. probabilistic, polynomial)называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее выходное значение совпадает с принадлежностью входа данным языкам больше $\frac{1}{2}$ и время ее работы ограничено полиномом от длины входа. $\mbox{PP} = \{L | \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) \gt \frac{1}{2} \}$ В этом определениях $m$ - это вероятностная машина Тьюринга.

Но это очень широкий класс, поэтому вводится класс $\mbox{BPP}$.

Определение класса BPP

Классом $\mbox{BPP}$ (от англ. bounded-error, probabilistic, polynomial) называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее выходное значение совпадает с принадлежностью входа данным языкам больше $\frac{2}{3}$ и время ее работы ограничено полиномом от длины входа. $\mbox{BPP} = \{L | \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) \gt \frac{2}{3} \}$ , где $m$ -- вероятностная машина Тьюринга.

Очевидно, класс $\mbox{BPP} \in \mbox{PP}$. Число $\frac{2}{3}$ в определении выбрано произвольно: если вместо него выбрать любое число, строго большее $\frac{1}{2}$, то получится тот же самый класс. Это верно, поскольку если есть машина Тьюринга, распознающая язык с вероятностью ошибки $p$, то точность можно сколь угодно хорошо улучшить за счёт относительно небольшого прироста времени. Если мы запустим машину $n$ раз подряд, а в качестве результата возьмём результат большинства запусков, то вероятность ошибки упадёт до $\left(2 \sqrt{p(1-p)} \right)^n$, а время станет равным $O(n^{k+1})$. Здесь $n$ запусков машины рассматриваются как схема Бернулли с $n$ испытаниями и вероятностью успеха 1-p, а формула, выражающая ошибку, — вероятность неудачи не менее чем в половине случаев. Если теперь запустить машину $n^{2}$ раз подряд, то время возрастёт до $O(n^{k+2})$, а вероятность ошибки упадёт до $\left(2 \sqrt{p(1-p)} \right)^{n^2}$. Таким образом, с ростом показателя многочлена, оценивающего время, точность растёт экспоненциально, и можно достичь любого нужного значения.