Теорема о включении BPP в P/poly — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
(Доказательство)
Строка 5: Строка 5:
 
== Доказательство ==
 
== Доказательство ==
  
Для доказательства данной теоремы воспользуемся сильным определением <math> BPP </math>. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <math> x </math> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <math> BPP </math> и добьёмся вероятности ошибки <math> \frac{1}{2^{n+1}}</math>, где <math> n = |x| </math> (длина входа). Будем говорить, что <math> r </math> "плохо" для <math> x </math>, если ответ неверный. Пусть <math> t </math> общее количество выборов для <math> r </math>. Для каждого <math> x </math> по крайне мере <math> \frac{t}{2^{n+1}}</math> "плохих" значений <math> r</math>. Cуммирую по всем <math> x </math>, мы получим, что по крайне мере <math> \frac{t*2^{n}}{2^{n+1}}</math> "плохих" <math> r </math> для <math> x </math>. С другой стороны, хотя бы <math> t/2 </math> значений <math> r </math> не "плохи" для любого <math> x </math>. Получается, что точно найдётся такое <math> r </math>, при котором будет получается всегда верный результат. Таким образом мы получили, что язык из <math> BPP </math> принадлежит <math>P/poly</math>.
+
Для доказательства данной теоремы воспользуемся сильным определением [[Сложностный_класс_BPP|BPP]]. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <tex> x </tex> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <tex> BPP </tex> и добьёмся вероятности ошибки <tex> \frac{1}{2^{n+1}}</tex>, где <tex> n = |x| </tex> (длина входа). Будем говорить, что <tex> r </tex> "плохо" для <tex> x </tex>, если ответ неверный. Пусть <tex> t </tex> общее количество выборов для <tex> r </tex>. Для каждого <tex> x </tex> по крайне мере <tex> \frac{t}{2^{n+1}}</tex> "плохих" значений <tex> r</tex>. Cуммирую по всем <tex> x </tex>, мы получим, что по крайне мере <tex> \frac{t*2^{n}}{2^{n+1}}</tex> "плохих" <tex> r </tex> для <tex> x </tex>. С другой стороны, хотя бы <tex> t/2 </tex> значений <tex> r </tex> не "плохи" для любого <tex> x </tex>. Получается, что точно найдётся такое <tex> r </tex>, при котором будет получается всегда верный результат. Таким образом мы получили, что язык из <tex> BPP </tex> принадлежит <tex>P/poly</tex>.

Версия 03:48, 17 июня 2010

Формулировка

[math]BPP \subset P/poly[/math]

Доказательство

Для доказательства данной теоремы воспользуемся сильным определением BPP. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа [math] x [/math] c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из [math] BPP [/math] и добьёмся вероятности ошибки [math] \frac{1}{2^{n+1}}[/math], где [math] n = |x| [/math] (длина входа). Будем говорить, что [math] r [/math] "плохо" для [math] x [/math], если ответ неверный. Пусть [math] t [/math] общее количество выборов для [math] r [/math]. Для каждого [math] x [/math] по крайне мере [math] \frac{t}{2^{n+1}}[/math] "плохих" значений [math] r[/math]. Cуммирую по всем [math] x [/math], мы получим, что по крайне мере [math] \frac{t*2^{n}}{2^{n+1}}[/math] "плохих" [math] r [/math] для [math] x [/math]. С другой стороны, хотя бы [math] t/2 [/math] значений [math] r [/math] не "плохи" для любого [math] x [/math]. Получается, что точно найдётся такое [math] r [/math], при котором будет получается всегда верный результат. Таким образом мы получили, что язык из [math] BPP [/math] принадлежит [math]P/poly[/math].