Классы BPP и PP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Закончены доказательства.)
Строка 18: Строка 18:
 
[[Вероятностная машина Тьюринга|ВМТ]] <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}: 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_{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>m_{2}</math> будет работать таким образом:
 
Машина <math>m_{2}</math> будет работать таким образом:
 
запустим <math>~N_{str}(p(|x|),m_{1})</math> раз машину <math>m_{1}</math>, запоминая результат каждого запуска.
 
запустим <math>~N_{str}(p(|x|),m_{1})</math> раз машину <math>m_{1}</math>, запоминая результат каждого запуска.
 
Вернем <math>1</math>, если больше половины запусков вернули <math>1</math>. Иначе вернем <math>0</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}</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>~N_{str}(p|x|,m_{1})</math>======
 
При запуске машины <math>m_{2}</math> все запуски <math>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>m_{1}</math> возвращает правильный ответ с вероятностью <math>p \geq 2/3 > 1/2</math>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <math>P(m_{2}(x) = [x \in L])</math>:<br>
Строка 34: Строка 34:
 
[[Вероятностная машина Тьюринга|ВМТ]] <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}: 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_{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>~m_{2}</math>=====
 
Машина <math>m_{2}</math> будет работать таким образом:
 
Машина <math>m_{2}</math> будет работать таким образом:
 
запустим <math>~N_{str}(p(|x|),m_{1})</math> раз машину <math>m_{1}</math>, запоминая результат каждого запуска.
 
запустим <math>~N_{str}(p(|x|),m_{1})</math> раз машину <math>m_{1}</math>, запоминая результат каждого запуска.
 
Вернем <math>1</math>, если больше половины запусков вернули <math>1</math>. Иначе вернем <math>0</math>.
 
Вернем <math>1</math>, если больше половины запусков вернули <math>1</math>. Иначе вернем <math>0</math>.
 
Если <math>N_{weak}</math> таково, что <math>P(m_{2}(x) = [x \in L]) > 2/3) \and N_{weak} \in poly(|x|)</math>, то искомая машина построена.
 
Если <math>N_{weak}</math> таково, что <math>P(m_{2}(x) = [x \in L]) > 2/3) \and N_{weak} \in poly(|x|)</math>, то искомая машина построена.
======Построение <math>N_{weak}(p|x|,m_{1})</math>======
+
======Построение <math>~N_{weak}(p|x|,m_{1})</math>======
 
При запуске машины <math>m_{2}</math> все запуски <math>m_{1}</math> можно считать независимыми, причем каждый запуск
 
При запуске машины <math>m_{2}</math> все запуски <math>m_{1}</math> можно считать независимыми, причем каждый запуск
 
<math>m_{1}</math> возвращает правильный ответ с вероятностью <math>p = 1/2 + 1/p(|x|) > 1/2</math>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <math>P(m_{2}(x) = [x \in L])</math>:<br>
 
<math>m_{1}</math> возвращает правильный ответ с вероятностью <math>p = 1/2 + 1/p(|x|) > 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_{weak}}{2}\mathcal{c}+1}^{N_{weak}}[{N_{weak}\choose i} p^{i}(1-p)^{N_{weak}-i}]</math>. Тогда, по неравенству Чернова: <math>P(m_{2}(x) = [x \in L]) \geq 1 - e^{-2N_{weak}(p-1/2)^2}</math>. Достаточно подобрать такое <math>N_{weak}</math>, чтобы <math>1 - e^{-2N_{weak}(p-1/2)^2} \geq 2/3</math>. Несложными преобразованиями получаем <math>N_{weak} \geq \frac{\ln 3}{2(1/2 +1/p(|x|)-1/2)^2} = \frac{p(|x|)^2 \ln 3}{2}</math>, т.е. можем выбрать <math>N_{weak} \in poly(|x|)</math>.
 
<math>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}]</math>. Тогда, по неравенству Чернова: <math>P(m_{2}(x) = [x \in L]) \geq 1 - e^{-2N_{weak}(p-1/2)^2}</math>. Достаточно подобрать такое <math>N_{weak}</math>, чтобы <math>1 - e^{-2N_{weak}(p-1/2)^2} \geq 2/3</math>. Несложными преобразованиями получаем <math>N_{weak} \geq \frac{\ln 3}{2(1/2 +1/p(|x|)-1/2)^2} = \frac{p(|x|)^2 \ln 3}{2}</math>, т.е. можем выбрать <math>N_{weak} \in poly(|x|)</math>.

Версия 14:53, 15 апреля 2010

Определения

[math]BPP = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) \gt 2/3\}[/math]
где [math]m[/math] -- вероятностная машина Тьюринга.
Существуют альтернативные определения класса [math]BPP[/math]:

  • [math]BPP_{weak} = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) \gt 1/2 + 1/p(|x|)\}[/math]

где [math]m[/math] -- ВМТ, а [math]~p(|x|): \forall x: p(|x|) \gt 2[/math] -- полином.

  • [math]BPP_{strong} = \{L |{ }\exist m: T(m,x) = Poly(|x|) \and P(m(x) = [x \in L]) \gt 1 - 2^{-p(|x|)}\}[/math]

где [math]m[/math] -- ВМТ, а [math]~p(|x|)[/math] -- полином.

Эквивалентность определений

Требуется доказать, что [math]~BPP_{strong} = BPP= BPP_{weak}[/math].
Для доказательства обоих равенств потребуется неравенство Чернова:

[math]\forall p \gt 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}}[/math]

Доказательство [math]~BPP_{strong} = BPP[/math]

Очевидно, что [math]~BPP_{strong} \subset BPP[/math].
Докажем обратное включение. Пусть [math]L \in BPP[/math], тогда существует ВМТ [math]m_{1}: T(m_{1},x) = Poly(|x|) \and P(m_{1}(x) = [x \in L]) \gt 2/3[/math]. Построим ВМТ [math]m_{2}: T(m_{2},x) = Poly(|x|) \and P(m_{2}(x) = [x \in L]) \gt 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]) \gt 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 \gt 1/2[/math]. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е [math]P(m_{2}(x) = [x \in L])[/math]:
[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]


Доказательство [math]~BPP_{weak} = BPP[/math]

Очевидно, что [math]~BPP \subset BPP_{weak}[/math].
Докажем обратное включение. Пусть [math]L \in BPP_{weak}[/math], тогда существует ВМТ [math]m_{1}: T(m_{1},x) = Poly(|x|) \and P(m_{1}(x) = [x \in L]) \gt 1/2 + 1/p(|x|)[/math]. Построим ВМТ [math]m_{2}: T(m_{2},x) = Poly(|x|) \and P(m_{2}(x) = [x \in L]) \gt 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]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_{weak}[/math] таково, что [math]P(m_{2}(x) = [x \in L]) \gt 2/3) \and N_{weak} \in poly(|x|)[/math], то искомая машина построена.

Построение [math]~N_{weak}(p|x|,m_{1})[/math]

При запуске машины [math]m_{2}[/math] все запуски [math]m_{1}[/math] можно считать независимыми, причем каждый запуск [math]m_{1}[/math] возвращает правильный ответ с вероятностью [math]p = 1/2 + 1/p(|x|) \gt 1/2[/math]. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е [math]P(m_{2}(x) = [x \in L])[/math]:
[math]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}][/math]. Тогда, по неравенству Чернова: [math]P(m_{2}(x) = [x \in L]) \geq 1 - e^{-2N_{weak}(p-1/2)^2}[/math]. Достаточно подобрать такое [math]N_{weak}[/math], чтобы [math]1 - e^{-2N_{weak}(p-1/2)^2} \geq 2/3[/math]. Несложными преобразованиями получаем [math]N_{weak} \geq \frac{\ln 3}{2(1/2 +1/p(|x|)-1/2)^2} = \frac{p(|x|)^2 \ln 3}{2}[/math], т.е. можем выбрать [math]N_{weak} \in poly(|x|)[/math].