202
правки
Изменения
кат
==Определения==
{{Определение
|definition =
<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых существует такая [[Вероятностные вычисления. Вероятностная машина Тьюринга |ВМТ]] <tex>p</tex>, что для любого <tex>x</tex>:
# <tex>P(p(x) = [x \in L]) \ge 2/3</tex>;
# <tex>T(p, x) \le poly(|x|)</tex> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
}}
<tex>\mathrm{BPP}</tex> — сложностный класс, допускающий двусторонние ошибки.
Константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>, так как требуемой вероятности можно добиться множественным запуском <tex>p</tex>. Замена константы на <tex>1/2</tex> сделала бы данный класс равным <tex>\Sigma^*</tex> (программа, возвращающая результат функции ''random''(), подошла бы для любого языка).
{{Определение
|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> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
}}
<tex>\mathrm{BPP_{strong}}</tex> — класс языков <tex>L</tex>, для которых существует такая ВМТ <tex>p</tex>, что для любого <tex>x</tex>:
#<tex>P(p(x)=[x \in L]) \ge 1 - \frac {1} {2^{q(|x|)}}</tex>, где <tex>q</tex>-полином и <tex>q(|x|) \ge 3</tex>;
#<tex>T(p(, x)) \le poly(|x|)</tex> для любой вероятностной ленты.
}}
==Теорема==
{{Теорема
|statement= <tex>\mathrm{BPP}</tex><ref>[[Вероятностные вычисления. Вероятностная машина Тьюринга]]</ref> <tex>= \mathrm{BPP_{weak}} = \mathrm{BPP_{strong}}</tex>.
|proof=
В доказательстве будет использоваться ''неравенство Чернова'': <br>
}}
{{Теорема|statement =<tex>\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}</tex>.|proof =Пусть <tex>p</tex> — программа для <tex>L \in \mathrm{RP}</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом: <tex>q</tex>(x) u <- <tex>p</tex>(x) v <- <tex>p</tex>(x) '''return''' u '''or''' vПусть <tex>x \in L</tex>. В этом случае вероятность ошибки равна <tex>\operatorname{P}(u =0, v = Ссылки 0) =\operatorname{P}(u =0) \cdot \operatorname{P}(v = 0) \le 1/4</tex>. Пусть <tex>x \notin L</tex>. Тогда с вероятностью <tex>1</tex> будет верно <tex>u = 0, v = 0<references/tex>и <tex>q</tex> вернет правильный ответ. Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.}} == См. также ==* [[Вероятностные вычисления. Вероятностная машина Тьюринга]] <br>* [http://en.wikipedia.org/wiki/Chernoff_bound Неравенство Чернова] [[Категория:Классы сложности]][[Категория:Теория формальных языков]]
