141
правка
Изменения
Попытка исправить
Если <tex>2^t\left(1 - \frac{|X|}{2^t}\right)^k < 1</tex>, то существует такой набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>, что <tex>\bigcup\limits_{i=1}^{k} g_i \oplus X = G</tex>, то есть <tex>X</tex> — <tex>k</tex>-большое.
Рассмотрим язык <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>Mm</tex>достаточное число раз, что чтобы получить вероятность ошибки <tex>P(M(x) = [x \in L]) \geqslant 1 - \frac{1}{2^{p(n)}}</tex>, где <tex>p(n)</tex> это некоторый полином, который будет определен определён позднее. Пусть Будет достаточно <tex>c p(n)^2</tex> запусков. Соответственно, <tex>M</tex> использует <tex>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\}^{r(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>-большое.
