Изменения

<tex>\mathrm{BPP_{weak}}</tex> — класс языков <tex>L</tex>, для которых существует такая [[Вероятностные вычисления. Вероятностная машина Тьюринга |ВМТ]] <tex>p</tex>, такая, что для любого <tex>x</tex>:

<tex>\mathrm{BPP_{strong}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, такая, что для любого <tex>x</tex>:

# <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex> <br> Пусть <tex>L \in \mathrm{BPP_{weak}}</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}</tex>. <br> Построим [[Вероятностные вычисления. Вероятностная машина Тьюринга |ВМТ]] <tex>p_1</tex>, которая для входа <tex>x</tex> запускает <tex>p(x)</tex> <tex>n</tex> раз, и, если больше половины запусков принимают <tex>x</tex>, то <tex>p_1</tex> принимает <tex>x</tex>. <br> Подберем <tex>n</tex>, такое, что <tex>P(p_1(x)=[x \in L]) \ge \frac {2}{3}</tex> и <tex>T(p_1(x)) \le poly(|x|)</tex>. <br> Вероятность <tex>P</tex> того, что <tex>p_1(x)</tex> даст правильный результат равна вероятности, что больше половины запусков <tex>p(x)</tex> дадут правильный результат. Тогда по схеме Бернулли <tex>P = \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i}</tex>, где <tex>p=\frac {1}{2} + \frac {1} {q(|x|)}</tex> — вероятность, что запуск <tex>p(x)</tex> даст правильный ответ. По неравенству Чернова <tex> P \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} </tex>. То есть для того, чтобы <tex>P(p(x)=[x \in L]) \ge \frac {2}{3}</tex> достаточно подобрать <tex>n</tex>, такое что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge \frac {2}{3}</tex>. Получаем, что <tex>n \ge \frac {\ln 3} {2(p - \frac {1} {2})^2} = \frac {{q(|x|)}^2 \ln 3}{2} </tex>. Следовательно, мы можем взять <tex>n</tex> такое, что <tex>T(p_1(x)) \le poly(|x|)</tex>