Изменения

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

#<tex>T(p(, x)) \le poly(|x|)</tex> для любой вероятностной ленты.

<tex>\mathrm{BPP_{strong}}</tex> — множество класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, такая, что для любого <tex>x</tex>:#<tex>P(p(x)=[x \in L]) \ge 1 - \frac {1 / } {2^{q(|x|)}}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;#<tex>T(p(, x)) \le poly(|x|)</tex> для любой вероятностной ленты.

|statement= <tex>\mathrm{BPP } = \mathrm{BPP_{weak}} = \mathrm{BPP_{strong}}</tex>.

Для доказательства теоремы будем использовать В доказательстве будет использоваться ''неравенство Чернова'': <br><tex>\forall p \ge : \frac {1} {2} \le p \le 1: \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i} \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2}</tex> 

* Докажем, что <tex>\mathrm{BPP } = \mathrm{BPP_{weakstrong}}</tex># <tex>BPP \mathrm{BPP_{strong}} \subseteq BPP_\mathrm{weakBPP}</tex> <br> Это понятно следует из определений <tex>\mathrm{BPP}</tex> и <tex>\mathrm{BPP_{weakstrong}}</tex>.# <tex>BPP_\mathrm{weakBPP} \subseteq BPP\mathrm{BPP_{strong}}</tex> <br> Пусть <tex>L \in BPP_\mathrm{weakBPP}</tex>. Тогда <tex>\exists p : P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)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|)}{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_mathrm{i = \lfloor \fracBPP_{nweak}{2} \rfloor + 1}^n subseteq \binommathrm{n}{i}p^i (1 - p)^{n - iBPP}</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 1 - \frac {1}{2^{q(|x|)}{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 {{q(|x|)} \ln 32} {2(p {\frac {2}{3} - \frac {1} {2}})^2} </tex>. Возьмем <tex>n = \frac {lceil 18 {q(|x|)}^2 \ln 3}{2} \rceil </tex>. Следовательно, мы можем взять <tex>n</tex> такое, что тогда неравенство <tex>T(p_1(x)) \le poly(|x|)</tex>будет выполнено.}}

* Докажем, что <tex>BPP {{Теорема|statement = BPP_{strong}</tex># <tex>BPP_\mathrm{strongRP} \subseteq BPP </tex> <br> Это понятно из определений <tex>BPP</tex> и <tex>BPP_cup \mathrm{strongcoRP}</tex>.# <tex>BPP \subseteq BPP_subset \mathrm{strongBPP}</tex> <br> .|proof =Пусть <tex>L \in BPPp</tex>. Тогда — программа для <tex>\exists p : P(p(x)=[x L \in L]) \ge \frac {2}mathrm{3RP}</tex>. <br> Построим ВМТ Программу <tex>p_1q</tex>, которая для входа <tex>x\mathrm{BPP}</tex> запускает определим следующим образом: <tex>pq</tex>(x) u </tex> - <tex>np</tex> раз, и, если больше половины запусков принимают <tex>(x) v </tex>, то - <tex>p_1p</tex> принимает (x) '''return''' u '''or''' vПусть <tex>x\in L</tex>. <br> Подберем <tex>n</tex>, такое, что В этом случае вероятность ошибки равна <tex>\operatorname{P}(p_1(xu = 0, v = 0)=[x \in L]operatorname{P}(u = 0) \ge 1 - cdot \frac operatorname{1P}{2^{q(|x|v = 0)}}\le 1/4</tex> и . Пусть <tex>T(p_1(x)) \le poly(|x|)notin L</tex>. Тогда с вероятностью <brtex>1</tex> Проводя рассуждения аналогичные изложенным в доказательстве будет верно <tex>BPP_{weak} \subseteq BPPu = 0, v = 0</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 mathrm{{q(|x|)coRP} \ln 2}{2({subset \frac mathrm{2}{3} - \frac {1}{2}})^2BPP} </tex>. Следовательно, мы можем взять <tex>n</tex> такое, что <tex>T(p_1(x)) \le poly(|x|)</tex>

* [[Вероятностные вычисления. Вероятностная машина Тьюринга]] <br>* [http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова] [[Категория:Классы сложности]][[Категория:Теория формальных языков]]