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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Закончены доказательства.)
(кат)
(не показано 8 промежуточных версий 4 участников)
Строка 1: Строка 1:
−
===Определения===
+
==Определения==
−
<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>
+
|definition =
−
Существуют альтернативные определения класса <math>BPP</math>:<br>
+
<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых существует такая [[Вероятностные вычисления. Вероятностная машина Тьюринга |ВМТ]] <tex>p</tex>, что для любого <tex>x</tex>:
−
*<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>
+
# <tex>P(p(x) = [x \in L]) \ge 2/3</tex>;
−
где <math>m</math> -- [[Вероятностная машина Тьюринга|ВМТ]], а <math>~p(|x|): \forall x:  p(|x|) > 2</math> -- полином.
+
# <tex>T(p, x) \le poly(|x|)</tex> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
−
*<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> -- полином.
+
<tex>\mathrm{BPP}</tex> — сложностный класс, допускающий двусторонние ошибки.
 +
Константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>, так как требуемой вероятности можно добиться множественным запуском <tex>p</tex>. Замена константы на <tex>1/2</tex> сделала бы данный класс равным <tex>\Sigma^*</tex> (программа, возвращающая результат функции ''random''(), подошла бы для любого языка).
  
−
===Эквивалентность определений===
+
{{Определение
−
Требуется доказать, что <math>~BPP_{strong} = BPP= BPP_{weak}</math>.<br>
+
|definition =
−
Для доказательства обоих равенств потребуется неравенство Чернова:<br>
+
<tex>\mathrm{PP}</tex> (от ''probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
−
<center><math>\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}}</math></center>
+
# <tex>\operatorname{P}(p(x) = [x \in L]) > 1/2</tex>;
 +
# <tex>\forall r \operatorname{T}(p, x) \le poly(|x|)</tex>.
 +
}}
 +
<tex>\mathrm{PP}</tex> также допускает двусторонние ошибки, но является более широким по сравнению с <tex>\mathrm{BPP}</tex>.
  
−
====Доказательство <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>====
+
{{Определение
−
Очевидно, что <math>~BPP \subset BPP_{weak}</math>.<br>
+
|definition=
−
Докажем обратное включение. Пусть <math>L \in BPP_{weak}</math>, тогда существует
+
<tex>\mathrm{BPP_{strong}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:
−
[[Вероятностная машина Тьюринга|ВМТ]] <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>,
+
#<tex>P(p(x)=[x \in L]) \ge 1 - \frac {1} {2^{q(|x|)}}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;
−
используя заданные <math>m_{1}</math> и <math>~p(|x|)</math>. Если нам это удастся, то <math>L \in BPP \Rightarrow BPP_{weak} \in BPP \Rightarrow ~BPP_{weak} = BPP</math>.
+
#<tex>T(p, x) \le poly(|x|)</tex> для любой вероятностной ленты.
−
=====Построение <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]) > 2/3) \and N_{weak} \in poly(|x|)</math>, то искомая машина построена.
+
|statement= <tex>\mathrm{BPP} = \mathrm{BPP_{weak}} = \mathrm{BPP_{strong}}</tex>.
−
======Построение <math>N_{weak}(p|x|,m_{1})</math>======
+
|proof=
−
При запуске машины <math>m_{2}</math> все запуски <math>m_{1}</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>
+
<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>
−
<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>.
+
 
 +
 
 +
* Докажем, что <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> Пусть <tex>L \in \mathrm{BPP_{weak}}</tex>. Тогда <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> дадут правильный результат. Тогда по схеме Бернулли <tex>P = \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i}</tex>, где <tex>p=\frac {1}{2} + \frac {1} {q(|x|)}</tex> — вероятность, что запуск <tex>p(x)</tex> даст правильный ответ. По неравенству Чернова : <tex> P \ge 1 - \mathrm{e}^{- 2n \left( {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} {2})^2} = \frac {{q(|x|)}^2 \ln 3}{2} </tex>. Возьмем <tex>n = \lceil \frac {{q(|x|)}^2 \ln 3}{2} \rceil </tex>, тогда неравенство <tex>T(p_1(x)) \le poly(|x|)</tex> будет выполнено.
 +
 
 +
* Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{strong}}</tex>
 +
# <tex>\mathrm{BPP_{strong}} \subseteq \mathrm{BPP} </tex> <br> Это следует из определений <tex>\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(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]) \ge 1 - \frac {1}{2^{q(|x|)}}</tex> и <tex>T(p_1(x)) \le poly(|x|)</tex>. <br> Проводя рассуждения, аналогичные изложенным в доказательстве <tex>\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}</tex>, получаем, что <tex>1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge 1 - \frac {1}{2^{q(|x|)}}</tex>, где <tex>p = \frac {2} {3}</tex>. Отсюда <tex>n \ge \frac {{q(|x|)} \ln 2}{2({\frac {2}{3} - \frac {1}{2}})^2} </tex>. Возьмем <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]
 +
 
 +
[[Категория:Классы сложности]]
 +
[[Категория:Теория формальных языков]]

Версия 16:04, 14 ноября 2018

Определения

Определение:
[math]\mathrm{BPP}[/math] (от bounded probabilistic polynomial) — множество языков [math]L[/math], для которых существует такая ВМТ [math]p[/math], что для любого [math]x[/math]:
  1. [math]P(p(x) = [x \in L]) \ge 2/3[/math];
  2. [math]T(p, x) \le poly(|x|)[/math] для любой вероятностной ленты.

[math]\mathrm{BPP}[/math] — сложностный класс, допускающий двусторонние ошибки. Константу [math]2/3[/math] можно заменить на любое число из промежутка [math](1/2, 1)[/math], так как требуемой вероятности можно добиться множественным запуском [math]p[/math]. Замена константы на [math]1/2[/math] сделала бы данный класс равным [math]\Sigma^*[/math] (программа, возвращающая результат функции random(), подошла бы для любого языка).


Определение:
[math]\mathrm{PP}[/math] (от probabilistic polynomial) — множество языков [math]L[/math], для которых [math]\exists p \forall x[/math]:
  1. [math]\operatorname{P}(p(x) = [x \in L]) \gt 1/2[/math];
  2. [math]\forall r \operatorname{T}(p, x) \le poly(|x|)[/math].

[math]\mathrm{PP}[/math] также допускает двусторонние ошибки, но является более широким по сравнению с [math]\mathrm{BPP}[/math].


Определение:
[math]\mathrm{BPP_{weak}}[/math] — класс языков [math]L[/math], для которых существует такая ВМТ [math]p[/math], что для любого [math]x[/math]:
  1. [math]P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}[/math], где [math]q[/math]-полином и [math]q(|x|) \ge 3[/math];
  2. [math]T(p, x) \le poly(|x|)[/math] для любой вероятностной ленты.


Определение:
[math]\mathrm{BPP_{strong}}[/math] — класс языков [math]L[/math], для которых существует такая ВМТ [math]p[/math], что для любого [math]x[/math]:
  1. [math]P(p(x)=[x \in L]) \ge 1 - \frac {1} {2^{q(|x|)}}[/math], где [math]q[/math]-полином и [math]q(|x|) \ge 3[/math];
  2. [math]T(p, x) \le poly(|x|)[/math] для любой вероятностной ленты.


Теорема

Теорема:
[math]\mathrm{BPP} = \mathrm{BPP_{weak}} = \mathrm{BPP_{strong}}[/math].
Доказательство:
[math]\triangleright[/math]

В доказательстве будет использоваться неравенство Чернова:
[math]\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}[/math]


  • Докажем, что [math]\mathrm{BPP} = \mathrm{BPP_{weak}}[/math]
  1. [math]\mathrm{BPP} \subseteq \mathrm{BPP_{weak}}[/math]
    Это следует из определений [math]\mathrm{BPP}[/math] и [math]\mathrm{BPP_{weak}}[/math].
  2. [math]\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}[/math]
    Пусть [math]L \in \mathrm{BPP_{weak}}[/math]. Тогда [math]\exists p : P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}[/math].
    Построим ВМТ [math]p_1[/math], которая для входа [math]x[/math] запускает [math]p(x)[/math] [math]n[/math] раз, и принимает [math]x[/math], если больше половины запусков принимают его.
    Подберем [math]n[/math], такое, что [math]P(p_1(x)=[x \in L]) \ge \frac {2}{3}[/math] и [math]T(p_1(x)) \le poly(|x|)[/math].
    Вероятность [math]P[/math] того, что [math]p_1(x)[/math] даст правильный результат равна вероятности, что больше половины запусков [math]p(x)[/math] дадут правильный результат. Тогда по схеме Бернулли [math]P = \sum\limits_{i = \lfloor \frac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i}[/math], где [math]p=\frac {1}{2} + \frac {1} {q(|x|)}[/math] — вероятность, что запуск [math]p(x)[/math] даст правильный ответ. По неравенству Чернова : [math] P \ge 1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} [/math]. То есть для того, чтобы [math]P(p(x)=[x \in L]) \ge \frac {2}{3}[/math] достаточно подобрать такое [math]n[/math], что [math]1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge \frac {2}{3}[/math]. Получаем, что [math]n \ge \frac {\ln 3} {2(p - \frac {1} {2})^2} = \frac {{q(|x|)}^2 \ln 3}{2} [/math]. Возьмем [math]n = \lceil \frac {{q(|x|)}^2 \ln 3}{2} \rceil [/math], тогда неравенство [math]T(p_1(x)) \le poly(|x|)[/math] будет выполнено.
  • Докажем, что [math]\mathrm{BPP} = \mathrm{BPP_{strong}}[/math]
  1. [math]\mathrm{BPP_{strong}} \subseteq \mathrm{BPP} [/math]
    Это следует из определений [math]\mathrm{BPP}[/math] и [math]\mathrm{BPP_{strong}}[/math].
  2. [math]\mathrm{BPP} \subseteq \mathrm{BPP_{strong}}[/math]
    Пусть [math]L \in \mathrm{BPP}[/math]. Тогда [math]\exists p : P(p(x)=[x \in L]) \ge \frac {2}{3}[/math].
    Построим ВМТ [math]p_1[/math], которая для входа [math]x[/math] запускает [math]p(x)[/math] [math]n[/math] раз, и принимает [math]x[/math], если больше половины запусков принимают его.
    Подберем [math]n[/math], такое, что [math]P(p_1(x)=[x \in L]) \ge 1 - \frac {1}{2^{q(|x|)}}[/math] и [math]T(p_1(x)) \le poly(|x|)[/math].
    Проводя рассуждения, аналогичные изложенным в доказательстве [math]\mathrm{BPP_{weak}} \subseteq \mathrm{BPP}[/math], получаем, что [math]1 - \mathrm{e}^{- 2n \left( {p - \frac{1}{2}} \right)^2} \ge 1 - \frac {1}{2^{q(|x|)}}[/math], где [math]p = \frac {2} {3}[/math]. Отсюда [math]n \ge \frac {{q(|x|)} \ln 2}{2({\frac {2}{3} - \frac {1}{2}})^2} [/math]. Возьмем [math]n = \lceil 18 {q(|x|)} \ln 2 \rceil [/math], тогда неравенство [math]T(p_1(x)) \le poly(|x|)[/math] будет выполнено.
[math]\triangleleft[/math]

См. также

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Классы_BPP_и_PP&oldid=66963»