Изменения

Требуется доказать, что <mathtex>~BPP_{strong} = BPP= BPP_{weak}</mathtex>.<br>

<center><mathtex>\forall p > 1/2:~ \sum_{\mathcal{b}\frac{n}{2}\mathcal{c}+1}^{n}[{{{n\choose i}} p^{i}(1-p)^{n-i}] \geq 1 - e^{-2n(p-1/2)^2}}</mathtex></center>

===Доказательство <mathtex>~BPP_{strong} = BPP</mathtex>===Очевидно, что <mathtex>~BPP_{strong} \subset BPP</mathtex>.<br>Докажем обратное включение. Пусть <mathtex>L \in BPP</mathtex>, тогда существует[[Вероятностная машина Тьюринга|ВМТ]] <mathtex>m_{1}: T(m_{1},x) = Poly(|x|) \and wedge P(m_{1}(x) = [x \in L]) > 2/3</mathtex>. Построим [[Вероятностная машина Тьюринга|ВМТ]] <mathtex>m_{2}: T(m_{2},x) = Poly(|x|) \and wedge P(m_{2}(x) = [x \in L]) >1 - 2^{-p(|x|)}</mathtex>,используя заданные <mathtex>m_{1}</mathtex> и <mathtex>~p(|x|)</mathtex>. Если нам это удастся, то <mathtex>L \in BPP_{strong} \Rightarrow BPP \in BPP_{strong} \Rightarrow ~BPP_{strong} = BPP</mathtex>.====Построение <mathtex>~m_{2}</mathtex>====Машина <mathtex>m_{2}</mathtex> будет работать таким образом:запустим <mathtex>~N_{str}(p(|x|),m_{1})</mathtex> раз машину <mathtex>m_{1}</mathtex>, запоминая результат каждого запуска.Вернем <mathtex>1</mathtex>, если больше половины запусков вернули <mathtex>1</mathtex>. Иначе вернем <mathtex>0</mathtex>.Если <mathtex>N_{str}</mathtex> таково, что <mathtex>P(m_{2}(x) = [x \in L]) >1 - 2^{-p(|x|)} \and wedge N_{str} \in poly(|x|)</mathtex>, то искомая машина построена.=====Построение <mathtex>~N_{str}(p|x|,m_{1})</mathtex>=====При запуске машины <mathtex>m_{2}</mathtex> все запуски <mathtex>m_{1}</mathtex> можно считать независимыми, причем каждый запуск<mathtex>m_{1}</mathtex> возвращает правильный ответ с вероятностью <mathtex>p \geq 2/3 > 1/2</mathtex>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <mathtex>P(m_{2}(x) = [x \in L])</mathtex>:<br><mathtex>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}]</mathtex>. Тогда, по неравенству Чернова: <mathtex>P(m_{2}(x) = [x \in L]) \geq 1 - e^{-2N_{str}(p-1/2)^2}</mathtex>. Достаточно подобрать такое <mathtex>N_{str}</mathtex>, чтобы <mathtex>1 - e^{-2N_{str}(p-1/2)^2} \geq 1 - 2^{-p(|x|)}</mathtex>. Несложными преобразованиями получаем <mathtex>N_{str} \geq \frac{p(|x|) \ln 2}{2(p-1/2)^2}</mathtex>, т.е. можем выбрать <mathtex>N_{str} \in poly(|x|)</mathtex>

===Доказательство <mathtex>~BPP_{weak} = BPP</mathtex>===Очевидно, что <mathtex>~BPP \subset BPP_{weak}</mathtex>.<br>Докажем обратное включение. Пусть <mathtex>L \in BPP_{weak}</mathtex>, тогда существует[[Вероятностная машина Тьюринга|ВМТ]] <mathtex>m_{1}: T(m_{1},x) = Poly(|x|) \and wedge P(m_{1}(x) = [x \in L]) > 1/2 + 1/p(|x|)</mathtex>. Построим [[Вероятностная машина Тьюринга|ВМТ]] <mathtex>m_{2}: T(m_{2},x) = Poly(|x|) \and wedge P(m_{2}(x) = [x \in L]) >2/3</mathtex>,используя заданные <mathtex>m_{1}</mathtex> и <mathtex>~p(|x|)</mathtex>. Если нам это удастся, то <mathtex>L \in BPP \Rightarrow BPP_{weak} \in BPP \Rightarrow ~BPP_{weak} = BPP</mathtex>.====Построение <mathtex>~m_{2}</mathtex>====Машина <mathtex>m_{2}</mathtex> будет работать таким образом:запустим <mathtex>~N_{str}(p(|x|),m_{1})</mathtex> раз машину <mathtex>m_{1}</mathtex>, запоминая результат каждого запуска.Вернем <mathtex>1</mathtex>, если больше половины запусков вернули <mathtex>1</mathtex>. Иначе вернем <mathtex>0</mathtex>.Если <mathtex>N_{weak}</mathtex> таково, что <mathtex>P(m_{2}(x) = [x \in L]) > 2/3) \and wedge N_{weak} \in poly(|x|)</mathtex>, то искомая машина построена.=====Построение <mathtex>~N_{weak}(p|x|,m_{1})</mathtex>=====При запуске машины <mathtex>m_{2}</mathtex> все запуски <mathtex>m_{1}</mathtex> можно считать независимыми, причем каждый запуск<mathtex>m_{1}</mathtex> возвращает правильный ответ с вероятностью <mathtex>p = 1/2 + 1/p(|x|) > 1/2</mathtex>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <mathtex>P(m_{2}(x) = [x \in L])</mathtex>:<br><mathtex>P(m_{2}(x) = [x \in L]) = \sum_{\mathcal{b}\frac{N_{weak}}{2}\mathcal{c}+1}^{N_{weak}}[{N_{weak}\choose i} p^{i}(1-p)^{N_{weak}-i}]</mathtex>. Тогда, по неравенству Чернова: <mathtex>P(m_{2}(x) = [x \in L]) \geq 1 - e^{-2N_{weak}(p-1/2)^2}</mathtex>. Достаточно подобрать такое <mathtex>N_{weak}</mathtex>, чтобы <mathtex>1 - e^{-2N_{weak}(p-1/2)^2} \geq 2/3</mathtex>. Несложными преобразованиями получаем <mathtex>N_{weak} \geq \frac{\ln 3}{2(1/2 +1/p(|x|)-1/2)^2} = \frac{p(|x|)^2 \ln 3}{2}</mathtex>, т.е. можем выбрать <mathtex>N_{weak} \in poly(|x|)</mathtex>.