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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема)
м (Теорема)
Строка 24: Строка 24:
 
* Докажем, что <tex>\mathrm{BPP} = \mathrm{BPP_{weak}}</tex>
 
* Докажем, что <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} \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>, то принимает <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_{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} = \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_{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>, то принимает <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> будет выполнено.
+
# <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> будет выполнено.
 
}}
 
}}
  
 
== Ссылки ==
 
== Ссылки ==
 
<references/>
 
<references/>

Версия 00:16, 3 июня 2012

Определения

Определение:
[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}[/math][1] [math]= \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]

Ссылки