Теорема о включении BPP в P/poly

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

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

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

Для доказательства данной теоремы воспользуемся сильным определением BPP. Возьмём случайную последовательность, как дополнительный вход r, который будет решать для любого входа [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 \cdot 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] r [/math] будет являться подсказкой для заданной длины [math] n [/math]. Таким образом мы получили, что язык из [math] BPP [/math] принадлежит [math]P/poly[/math].