Изменения

Для доказательства данной теоремы воспользуемся сильным определением <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>.