Изменения

Рассмотрим язык <tex>L \in \mathrm{BPP}</tex>. Тогда существует вероятностная машина Тьюринга <tex>m</tex>, такая что <tex>P(m(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Пусть <tex>m</tex> использует <tex>r(n)</tex> бит случайной ленты. По аналогии c [[Классы BPP и PP|доказательством]] <tex>\mathrm{BPP} = \mathrm{BPP_{strong}}</tex>, построим машину <tex>M</tex>, которая запускает <tex>m</tex> достаточное число раз, чтобы получить вероятность ошибки <tex>\frac{1}{2^{p(n)}}</tex>, где <tex>p(n)</tex> это некоторый полином, который будет определён позднее. Будет достаточно <tex>c p(n)^2</tex> запусков. Соответственно, <tex>M</tex> использует <tex>t(n) = c r(n) p(n)^2</tex> бит случайной ленты, <tex>P(M(x) = [x \in L]) \geqslant 1 - \frac{1}{2^{p(n)}}</tex>.

Зафиксируем <tex>x</tex>. Возьмем <tex>G = \{0, 1\}^{rt(n)}</tex>. Рассмотрим множество <tex>A_x = \{r \in G \bigm| M(x,r) = 1\}</tex>. Подберем теперь <tex>p(n)</tex> и <tex>k</tex> так, чтобы <tex>x \in L \Leftrightarrow A_x</tex> — <tex>k</tex>-большое.

Если <tex>x \in L</tex>, то <tex>P(M(x) = 1) = \frac{|A_x|}{2^{rt(n)}} \geqslant 1 - \frac{1}{2^{p(n)}} \Rightarrow |A_x| \geqslant 2^{rt(n)} \left( 1 - \frac{1}{2^{p(n)}} \right)</tex>. Значит <tex>2^{rt(n)} \left( 1 - \frac{|A_x|}{2^{rt(n)}} \right)^k \leqslant 2^{rt(n) - kp(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-большим потребуем <tex>2^{rt(n) - kp(n)} < 1</tex>.

Если <tex>x \not \in L</tex>, то <tex>P(M(x) = 1) = \frac{|A_x|}{2^{rt(n)}} \leqslant \frac{1}{2^{p(n)}} \Rightarrow |A_x| \leqslant 2^{rt(n) - p(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-маленьким потребуем <tex>2^{rt(n) - p(n)} < \frac{2^{rt(n)}}{k}</tex>.

Выберем <tex>p(n)</tex> так, чтобы <tex>\frac{rt(n)}{p(n)} < 2^{p(n)} - 2</tex> и <tex>k = \lceil \frac{rt(n)}{p(n)} \rceil + 1</tex>. Получаем <tex>\frac{rt(n)}{p(n)} < k < 2^{p(n)}</tex>, то есть <tex>x \in L \Leftrightarrow A_x</tex> — <tex>k</tex>-большое.