Изменения
Нет описания правки
<tex>\mathrm{BPP}</tex> можно определить как множество таких языков <tex>L</tex>, что <tex>x \in L \Leftrightarrow \exists</tex> «много» вероятностных лент <tex>y: R(x,y)</tex>. <tex>\Sigma_2</tex> определяется как множество <tex>\{ L \mid x \in L \Leftrightarrow \exists y \forall z R(x, y, z)\}</tex>. Таким образом, необходимо уметь записывать «<tex>\exists</tex> много» с помощью кванторов <tex>\exists\forall</tex>.
Рассмотрим язык <tex>G</tex> всех слов длины <tex>k</tex> над алфавитом <tex>= \{0, 1\}^t</tex> для некоторого <tex>kt</tex>, значение которого будет получено позже. Определим операцию <tex>\oplus</tex> над словами из этого языка как побитовое исключающее или.
Назовем <tex>X</tex>, содержащееся в <tex>G</tex>, <tex>k</tex>-большим, если существует набор <tex>g_1, g_2, \dots g_k{g_i\}_{i=1}^{k}</tex> такой, что <tex>\bigcup_bigcup\limits_{i=1}^{k} g_i \oplus X = G</tex>.
Если <tex>k|X| < |G|\frac{2^t}{k}</tex>, то <tex>X</tex> точно не является большим<tex>k</tex>-маленьким. Найдем достаточное условие, при котором <tex>X</tex> большойявляется <tex>k</tex>-большим.
Воспользуемся утверждением, что если вероятность <tex>P(x \in A) > 0</tex>, то существует <tex>x</tex> из <tex>A</tex>. Для этого
выберем случайно набор <tex>\{g_i\}_{i=1}^{k}</tex>.
Если <tex>|G|2^t\left(1 - \frac{|X|}{|G|2^t}\right)^k < 1</tex>, то существует набор <tex>\{g_i\}_{i=1}^{k}</tex>, такой что для любого <tex>y</tex> выполнено <tex>\bigvee_bigcup\limits_{i=1}^{k} y \in 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 1 - \frac{1}{2^{p(n)}}</tex>, распознающая этот язык, завершается за где <tex>p(|x|n)</tex> шагов и вероятность ошибки не превосходитнекоторый полином, который будет определен позднее. Пусть <tex>M</tex> использует <tex>\frac{1}{3pr(|x|n)}</tex>, это следует из того, что если запускать программу несколько раз, то время работы растет линейно, а вероятность ошибкиэкспоненциально уменьшаетсябит случайной ленты.
Зафиксируем <tex>x</tex>. Возьмем <tex>k G = p\{0, 1\}^{r(|x|n)}</tex>. Рассмотрим множество начал длины <tex>kA_x = \{r \in G \mid M(x,r) = 1\}</tex> вероятностных лент . Подберем теперь <tex>Xp(n)</tex>, на которыхмашина и <tex>Mk</tex> выдает единицутак, то есть чтобы <tex>X = \{y x \in G L \mid M(x,y) = 1\}Leftrightarrow A_x</tex> <tex>k</tex>-большое.
Если <tex>x \not \in L</tex>, то:* <tex>P(A_x) = \frac{|XA_x|}{|G|2^{r(n)}} \geqslant 1 - leqslant \frac1frac{3k1}</tex>;* <tex>1 - \frac{|X|2^{p(n)}}{\Rightarrow |GA_x|} \leqslant \frac12^{3kr(n) - p(n)}</tex>;* . Потребуем <tex>|G|\left2^{r(1 n) - p(n)} < \frac{|X|2^{r(n)}{|G|}\right)^k \leqslant |G| \left(\frac1{3k}\right)^k = \left(\frac2{3k}\right)^k < 1/tex>, чтобы <tex>A_x</tex>, что влечет за собой то, что было бы <tex>Xk</tex> большой-маленьким.
Таким образом, <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k, g_1, g_2, \dots, g_k } \forall y \bigvee_bigvee\limits_{i=1}^{k} y \in g_i \oplus XA_x</tex>, то есть <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k, g_1, g_2, \dots, g_k } \forall y \bigvee_bigvee\limits_{i=1}^{k} y \oplus g_i \in XA_x</tex>, то есть<tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k, g_1, g_2, \dots, g_k } \forall y \bigvee_bigvee\limits_{i=1}^{k} M(x, y \oplus g_i)</tex>,
а, значит, <tex>L \in \Sigma_2</tex>, <tex>\mathrm{BPP} \subset \Sigma_2</tex> и <tex>\mathrm{BPP} \subset \Sigma_2 \cap \Pi_2</tex>, что и требовалось доказать.
