18
правок
Изменения
определения + схема доказательств эквивалентности определений
===Определения===
<math>BPP = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) > 2/3\}</math><br>
где <math>m</math> -- [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]].<br>
Существуют альтернативные определения класса <math>BPP</math>:<br>
*<math>BPP_{weak} = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) > 1/2 + 1/p(|x|)\}</math><br>
где <math>m</math> -- [[Вероятностная машина Тьюринга|ВМТ]], а <math>~p(|x|): \forall x: p(|x|) > 2</math> -- полином.
*<math>BPP_{strong} = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) > 1 - 2^{-p(|x|)}\}</math><br>
где <math>m</math> -- [[Вероятностная машина Тьюринга|ВМТ]], а <math>~p(|x|)</math> -- полином.
===Эквивалентность определений===
Требуется доказать, что <math>~BPP_{strong} = BPP= BPP_{weak}</math>.<br>
Для доказательства обоих равенств потребуется неравенство Чернова:
<math>\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}}</math>
====Доказательство <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>~BPP_{weak} = BPP</math>====
Очевидно, что <math>~BPP \subset BPP_{weak}</math>.<br>
Докажем обратное включение. Пусть <math>L \in BPP_{weak}</math>, тогда существует
[[Вероятностная машина Тьюринга|ВМТ]] <math>m_{1}: T(m_{1},x) = Poly(|x|) \and P(m_{1}(x) = [x \in L]) > 1/2 + 1/p(|x|)</math>. Построим [[Вероятностная машина Тьюринга|ВМТ]] <math>m_{2}: T(m_{2},x) = Poly(|x|) \and P(m_{2}(x) = [x \in L]) >2/3</math>,
используя заданные <math>m_{1}</math> и <math>~p(|x|)</math>. Если нам это удастся, то <math>L \in BPP \Rightarrow BPP_{weak} \in BPP \Rightarrow ~BPP_{weak} = BPP</math>.
=====Построение <math>m_{2}</math>=====
<math>BPP = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) > 2/3\}</math><br>
где <math>m</math> -- [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]].<br>
Существуют альтернативные определения класса <math>BPP</math>:<br>
*<math>BPP_{weak} = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) > 1/2 + 1/p(|x|)\}</math><br>
где <math>m</math> -- [[Вероятностная машина Тьюринга|ВМТ]], а <math>~p(|x|): \forall x: p(|x|) > 2</math> -- полином.
*<math>BPP_{strong} = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) > 1 - 2^{-p(|x|)}\}</math><br>
где <math>m</math> -- [[Вероятностная машина Тьюринга|ВМТ]], а <math>~p(|x|)</math> -- полином.
===Эквивалентность определений===
Требуется доказать, что <math>~BPP_{strong} = BPP= BPP_{weak}</math>.<br>
Для доказательства обоих равенств потребуется неравенство Чернова:
<math>\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}}</math>
====Доказательство <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>~BPP_{weak} = BPP</math>====
Очевидно, что <math>~BPP \subset BPP_{weak}</math>.<br>
Докажем обратное включение. Пусть <math>L \in BPP_{weak}</math>, тогда существует
[[Вероятностная машина Тьюринга|ВМТ]] <math>m_{1}: T(m_{1},x) = Poly(|x|) \and P(m_{1}(x) = [x \in L]) > 1/2 + 1/p(|x|)</math>. Построим [[Вероятностная машина Тьюринга|ВМТ]] <math>m_{2}: T(m_{2},x) = Poly(|x|) \and P(m_{2}(x) = [x \in L]) >2/3</math>,
используя заданные <math>m_{1}</math> и <math>~p(|x|)</math>. Если нам это удастся, то <math>L \in BPP \Rightarrow BPP_{weak} \in BPP \Rightarrow ~BPP_{weak} = BPP</math>.
=====Построение <math>m_{2}</math>=====
