===Определения===<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_{strong} = BPP= BPP_\mathrm{weakPP}</mathtex>.(от ''probabilistic polynomial'') — множество языков <brtex>Для доказательства обоих равенств потребуется неравенство Чернова:L<br/tex>, для которых <center><mathtex>\exists p \forall p x</tex> 1/2:~ \sum_{# <tex>\mathcaloperatorname{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)^{n-i}] \geq 1 - e^{-2nle poly(p-1|x|)</2)^2tex>.}}<tex>\mathrm{PP}</mathtex>также допускает двусторонние ошибки, но является более широким по сравнению с <tex>\mathrm{BPP}</centertex>.
====Доказательство <math>~BPP_{strong} = BPP</math>====
Очевидно, что <math>~BPP_{strong} \subset BPP</math>.<br>
Докажем обратное включение. Пусть <math>L \in BPP</math>, тогда существует
[[Вероятностная машина Тьюринга|ВМТ]] <math>m_{1}: T(m_{1},x) = Poly(|x|) \and P(m_{1}(x) = [x \in L]) > 2/3</math>. Построим [[Вероятностная машина Тьюринга|ВМТ]] <math>m_{2}: T(m_{2},x) = Poly(|x|) \and P(m_{2}(x) = [x \in L]) >1 - 2^{-p(|x|)}</math>,
используя заданные <math>m_{1}</math> и <math>~p(|x|)</math>. Если нам это удастся, то <math>L \in BPP_{strong} \Rightarrow BPP \in BPP_{strong} \Rightarrow ~BPP_{strong} = BPP</math>.
=====Построение <math>m_{2}</math>=====
Машина <math>m_{2}</math> будет работать таким образом:
запустим <math>~N_{str}(p(|x|),m_{1})</math> раз машину <math>m_{1}</math>, запоминая результат каждого запуска.
Вернем <math>1</math>, если больше половины запусков вернули <math>1</math>. Иначе вернем <math>0</math>.
Если <math>N_{str}</math> таково, что <math>P(m_{2}(x) = [x \in L]) >1 - 2^{-p(|x|)} \and N_{str} \in poly(|x|)</math>, то искомая машина построена.
======Построение <math>N_{str}(p|x|,m_{1})</math>======
При запуске машины <math>m_{2}</math> все запуски <math>m_{1}</math> можно считать независимыми, причем каждый запуск
<math>m_{1}</math> возвращает правильный ответ с вероятностью <math>p \geq 2/3 > 1/2</math>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <math>P(m_{2}(x) = [x \in L])</math>:<br>
<math>P(m_{2}(x) = [x \in L]) = \sum_{\mathcal{b}\frac{N_{str}}{2}\mathcal{c}+1}^{N_{str}}[{N_{str}\choose i} p^{i}(1-p)^{N_{str}-i}]</math>. Тогда, по неравенству Чернова: <math>P(m_{2}(x) = [x \in L]) \geq 1 - e^{-2N_{str}(p-1/2)^2}</math>. Достаточно подобрать такое <math>N_{str}</math>, чтобы <math>1 - e^{-2N_{str}(p-1/2)^2} \geq 1 - 2^{-p(|x|)}</math>. Несложными преобразованиями получаем <math>N_{str} \geq \frac{p(|x|) \ln 2}{2(p-1/2)^2}</math>, т.е. можем выбрать <math>N_{str} \in poly(|x|)</math>
{{Определение
|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> для любой вероятностной ленты.
}}
====Доказательство <math>~BPP_{weak} = BPP</math>==={Определение|definition=Очевидно, что <mathtex>~BPP \subset mathrm{BPP_{weakstrong}}</math>.<brtex>Докажем обратное включение. Пусть — класс языков <mathtex>L \in BPP_{weak}</mathtex>, тогда для которых существует[[Вероятностная машина Тьюринга|такая ВМТ]] <mathtex>p</tex>m_{1}: T(m_{1},что для любого <tex>x) = Poly(|x|) \and </tex>:#<tex>P(m_{1}p(x) = [x \in L]) > \ge 1 - \frac {1} {2^{q(|x|)}}</2 + 1tex>, где <tex>q</ptex>-полином и <tex>q(|x|)\ge 3</mathtex>. Построим [[Вероятностная машина Тьюринга|ВМТ]] ;#<mathtex>m_{2}: T(m_{2}p,x) = Poly\le poly(|x|) </tex> для любой вероятностной ленты.}} ==Теорема=={{Теорема|statement= <tex>\mathrm{BPP} = \and P(m_mathrm{BPP_{2weak}}(x) = [x \in L]) mathrm{BPP_{strong}}</tex>2/3.|proof=В доказательстве будет использоваться ''неравенство Чернова'': </mathbr>,используя заданные <mathtex>m_\forall p : \frac {1}</math> и <math>~{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(|x|{p - \frac{1}{2}} \right)^2}</mathtex>. Если нам это удастся * Докажем, то что <mathtex>L \in mathrm{BPP } = \Rightarrow mathrm{BPP_{weak} }</tex># <tex>\in mathrm{BPP } \Rightarrow ~subseteq \mathrm{BPP_{weak} = }</tex> <br> Это следует из определений <tex>\mathrm{BPP}</mathtex>.=====Построение и <mathtex>m_\mathrm{BPP_{2weak}}</mathtex>=====.Машина # <mathtex>m_\mathrm{2BPP_{weak}} \subseteq \mathrm{BPP}</mathtex> <br> будет работать таким образом:запустим Пусть <mathtex>~N_L \in \mathrm{strBPP_{weak}}</tex>. Тогда <tex>\exists p : P(p(|x|),m_=[x \in L]) \ge \frac {1}{2} + \frac {1}{q(|x|)}</mathtex>. <br> раз машину Построим ВМТ <mathtex>m_{1}p_1</mathtex>, запоминая результат каждого запуска.Вернем которая для входа <tex>x</tex> запускает <mathtex>1p(x)</mathtex>, если больше половины запусков вернули <mathtex>1n</mathtex>. Иначе вернем раз, и принимает <mathtex>0x</mathtex>, если больше половины запусков принимают его.Если <mathbr> Подберем <tex>N_{weak}n</mathtex> таково, такое, что <mathtex>P(m_{2}p_1(x) = [x \in L]) > \ge \frac {2}{3}</3tex> и <tex>T(p_1(x)) \and N_{weak} \in le poly(|x|)</mathtex>. <br> Вероятность <tex>P</tex>того, то искомая машина построена.======Построение что <mathtex>N_{weak}p_1(p|x|,m_{1})</mathtex>======При запуске машины даст правильный результат равна вероятности, что больше половины запусков <mathtex>m_{2}p(x)</mathtex> все запуски дадут правильный результат. Тогда по схеме Бернулли <mathtex>m_P = \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}</math> можно считать независимыми, причем каждый запуск<math>m_^n \binom{n}{i}p^i (1- p)^{n - i}</mathtex> возвращает правильный ответ с вероятностью , где <mathtex>p = \frac {1/}{2 } + \frac {1/p} {q(|x|) > 1/2}</mathtex>. Тогда по схеме Бернулли — вероятность того, что больше половины запусков вернули запуск <tex>p(x)</tex> даст правильный ответ, т.е По неравенству Чернова : <mathtex>P \ge 1 - \mathrm{e}^{- 2n \left(m_{p - \frac{1}{2}} \right)^2}</tex>. То есть для того, чтобы <tex>P(p(x) = [x \in L])\ge \frac {2}{3}</mathtex>:достаточно подобрать такое <tex>n<br/tex>, что <mathtex>P1 - \mathrm{e}^{- 2n \left(m_{p - \frac{1}{2}} \right)^2} \ge \frac {2}{3}</tex>. Получаем, что <tex>n \ge \frac {\ln 3} {2(x) = [x p - \in L]frac {1} {2}) ^2} = \sum_frac {{q(|x|)}^2 \mathcalln 3}{b2}</tex>. Возьмем <tex>n = \lceil \frac{N_{weakq(|x|)}^2 \ln 3}{2}\mathcalrceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(|x|)</tex> будет выполнено. * Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{cstrong}+1}^</tex># <tex>\mathrm{N_BPP_{weakstrong}}[\subseteq \mathrm{N_BPP} </tex> <br> Это следует из определений <tex>\mathrm{weakBPP}</tex> и <tex>\choose imathrm{BPP_{strong}} p^</tex>.# <tex>\mathrm{iBPP}(1-p)^\subseteq \mathrm{N_BPP_{weakstrong}}-i</tex> <br> Пусть <tex>L \in \mathrm{BPP}]</mathtex>. Тогда, по неравенству Чернова: <mathtex>\exists p : P(m_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>, если больше половины запусков принимают его. <br> Подберем <tex>n</tex>, такое, что <tex>P(p_1(x) = [x \in L]) \geq ge 1 - e\frac {1}{2^{-2N_{weakq(|x|)}}</tex> и <tex>T(p_1(x)) \le poly(p-1/2|x|)^2}</mathtex>. Достаточно подобрать такое <mathbr> Проводя рассуждения, аналогичные изложенным в доказательстве <tex>N_\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</mathtex>, чтобы получаем, что <mathtex>1 - \mathrm{e}^{-2N_2n \left( {weak}(p-\frac{1/}{2}} \right)^2} \geq ge 1 - \frac {1}{2^{q(|x|)}}</tex>, где <tex>p = \frac {2} {3}</mathtex>. Несложными преобразованиями получаем Отсюда <mathtex>N_{weak} n \geq ge \frac{{q(|x|)} \ln 32}{2(1/{\frac {2 +1/p(|x|)}{3} -\frac {1/}{2}})^2} </tex>. Возьмем <tex>n = \fraclceil 18 {pq(|x|)^2 } \ln 3}{2}\rceil </mathtex>, т.е. можем выбрать тогда неравенство <mathtex>N_{weak} T(p_1(x)) \in le poly(|x|)</mathtex>будет выполнено.}} == См. также ==* [[Вероятностные вычисления. Вероятностная машина Тьюринга]] <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] [[Категория:Классы сложности]][[Категория:Теория формальных языков]]
