Изменения

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