Изменения

# <tex>BPP \subseteq BPP_{strong}</tex> <br> Пусть <tex>L \in BPP</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {2}{3}</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 1 - \frac {1}{2^{q(|x|)}}</tex> и <tex>T(p_1(x)) \le poly(|x|)</tex>. <br> Проводя рассуждения аналогичные изложенным в доказательстве <tex>BPP_{weak} \subseteq BPP</tex>, получаем, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge 1 - \frac {1}{2^{q(|x|)}}</tex>. Отсюда <tex>n \ge \frac {{q(|x|)} \ln 2}{2({\frac {2}{3} - \frac {1}{2}})^2} </tex>. Следовательно, мы можем взять <tex>n</tex> такое, что <tex>T(p_1(x)) \le poly(|x|)</tex>

}}