Теорема о включении 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> 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>. |
Версия 23:04, 22 апреля 2010
Формулировка
Доказательство
Для доказательства данной теоремы воспользуемся сильным определением . Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из и добьёмся вероятности ошибки , где (длина входа). Будем говорить, что "плохо" для , если ответ неверный. Пусть общее количество выборов для . Для каждого по крайне мере "плохих" значений . Cуммирую по всем , мы получим, что по крайне мере "плохих" для . С другой стороны, хотя бы значений не "плохи" для любого . Получается, что точно найдётся такое , при котором будет получается всегда верный результат. Таким образом мы получили, что язык из принадлежит .
