Изменения

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