Изменения

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