Изменения

===Определения===<math>BPP = \{L |{ }\exist m: T(m,x) = Poly(|xОпределение|) \and P(m(x) definition = [x \in L]) <tex> 2/3\mathrm{BPP}</mathtex>(от ''bounded probabilistic polynomial'') — множество языков <brtex>где <math>mL</mathtex> -- , для которых существует такая [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина ТьюрингаВМТ]].<brtex>p</tex>Существуют альтернативные определения класса , что для любого <mathtex>BPPx</mathtex>:<br>*# <mathtex>BPP_{weak} = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(mp(x) = [x \in L]) > 1\ge 2/2 + 13</tex>;# <tex>T(p, x) \le poly(|x|)\}</math><brtex>где <math>m</math> -- для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга|ВМТвероятностной ленты]], а .}}<mathtex>~p(|x|): \forall x: p(|x|) mathrm{BPP}</tex> — сложностный класс, допускающий двусторонние ошибки.Константу <tex> 2/3</mathtex> -- полином.*можно заменить на любое число из промежутка <mathtex>BPP_{strong} = \{L |{ }\exist m: T(m1/2,x) = Poly(|x|) \and P(m(x) = [x \in L]) > 1 - 2^{-p(|x|)}\}</mathtex>, так как требуемой вероятности можно добиться множественным запуском <brtex>p</tex>где . Замена константы на <mathtex>m1/2</mathtex> -- [[Вероятностная машина Тьюринга|ВМТ]], а сделала бы данный класс равным <mathtex>~p(|x|)\Sigma^*</mathtex> -- полином(программа, возвращающая результат функции ''random''(), подошла бы для любого языка).

===Эквивалентность определений=={{Определение|definition =Требуется доказать, что <mathtex>~BPP_\mathrm{strong} = BPP= BPP_{weakPP}</mathtex> (от ''probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>.\exists p \forall x<br/tex>Для доказательства обоих равенств потребуется неравенство Чернова:# <mathtex>\sum_operatorname{\mathcal{bP}(p(x) = [x \frac{n}{in L]) > 1/2}</tex>;# <tex>\mathcal{c}+1}^{n}[{{{nforall r \choose i}} p^operatorname{iT}(1-p, x) \le poly(|x|)^</tex>.}}<tex>\mathrm{n-iPP}] </tex> также допускает двусторонние ошибки, но является более широким по сравнению с <tex>\geq 1 - e^mathrm{-2n(p-1/2)^2}BPP}</mathtex>.

{{Определение|definition=<tex>\mathrm{BPP_{weak}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:#<tex>P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;#<tex>T(p, x) \le poly(|x|)</tex> для любой вероятностной ленты.}} {{Определение|definition==Доказательство <mathtex>~\mathrm{BPP_{weakstrong}} </tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:#<tex>P(p(x)= BPP[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|)</mathtex>для любой вероятностной ленты.}} ==Теорема==Очевидно, что {{Теорема|statement= <mathtex>~\mathrm{BPP } = \subset mathrm{BPP_{weak}} = \mathrm{BPP_{strong}}</mathtex>.|proof=В доказательстве будет использоваться ''неравенство Чернова'': <br><tex>\forall p : \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_{weak}}</tex># <tex>\mathrm{BPP} \subseteq \mathrm{BPP_{weak}}</tex> <br> Это следует из определений <tex>\mathrm{BPP}</tex> и <tex>\mathrm{BPP_{weak}}</tex>. # <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex> <br> Пусть <mathtex>L \in \mathrm{BPP_{weak}}</mathtex>, тогда существует. Тогда <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>, если больше половины запусков принимают его. <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> дадут правильный результат. Тогда по схеме Бернулли <mathtex>m_P = \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}: T^n \binom{n}{i}p^i (m_1 - p)^{1n - i}</tex>,x) где <tex>p= Poly\frac {1}{2} + \frac {1} {q(|x|) }</tex> — вероятность, что запуск <tex>p(x)</tex> даст правильный ответ. По неравенству Чернова : <tex> P \ge 1 - \mathrm{e}^{- 2n \and Pleft(m_{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/p} {2})^2} = \frac {{q(|x|)}^2 \ln 3}{2} </mathtex>. Построим [[Вероятностная машина Тьюринга|ВМТ]] Возьмем <mathtex>m_n = \lceil \frac {{q(|x|)}^2\ln 3}: T(m_{2}\rceil </tex>,тогда неравенство <tex>T(p_1(x) = Poly) \le poly(|x|) </tex> будет выполнено. * Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{strong}}</tex># <tex>\mathrm{BPP_{strong}} \subseteq \mathrm{BPP} </tex> <br> Это следует из определений <tex>\and mathrm{BPP}</tex> и <tex>\mathrm{BPP_{strong}}</tex>.# <tex>\mathrm{BPP} \subseteq \mathrm{BPP_{strong}}</tex> <br> Пусть <tex>L \in \mathrm{BPP}</tex>. Тогда <tex>\exists p : P(m_{2}p(x) = [x \in L]) \ge \frac {2}{3}</tex>. <br>2Построим ВМТ <tex>p_1</tex>, которая для входа <tex>x</tex> запускает <tex>p(x)</tex> <tex>n</tex> раз, и принимает <tex>x</3tex>, если больше половины запусков принимают его. <br> Подберем <tex>n</mathtex>,используя заданные такое, что <mathtex>m_P(p_1(x)=[x \in L]) \ge 1 - \frac {1}{2^{q(|x|)}}</mathtex> и <mathtex>~pT(p_1(x)) \le poly(|x|)</mathtex>. Если нам это удастся<br> Проводя рассуждения, то аналогичные изложенным в доказательстве <mathtex>L \in BPP \Rightarrow mathrm{BPP_{weak}} \in subseteq \mathrm{BPP }</tex>, получаем, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge 1 - \Rightarrow ~BPP_frac {1}{2^{weakq(|x|)}} </tex>, где <tex>p = BPP\frac {2} {3}</mathtex>.=====Построение Отсюда <mathtex>m_n \ge \frac {{q(|x|)} \ln 2}{2({\frac {2}{3} - \frac {1}{2}})^2}</mathtex>. Возьмем <tex>n =\lceil 18 {q(|x|)} \ln 2 \rceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(|x|)</tex> будет выполнено.}} ==См. также ==* [[Вероятностные вычисления. Вероятностная машина Тьюринга]] <br>* [http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова]* [http://en.wikipedia.org/wiki/PP_(complexity) Wikipedia — PP compexity class]* [http://en.wikipedia.org/wiki/Bounded-error_probabilistic_polynomial Wikipedia — BPP complexity class] [[Категория:Классы сложности]][[Категория:Теория формальных языков]]