Изменения
Нет описания правки
{{ Теорема
| about = Лаутеман
| statement = [[Вероятностные вычисления. Вероятностная машина Тьюринга | <tex>\mathrm{BPP}</tex>]] <tex>\subset</tex> [[Классы PH, Σ и Π | <tex>\mathrm{\Sigma_2} \cap \mathrm{\Pi_2}</tex>]]
| proof =
Из того, что класс <tex>\mathrm{BPP}</tex> замкнут относительно дополнения и <tex>\mathrm{co}\Sigma_2 = \Pi_2</tex>, следует, что достаточно доказать включение <tex>\mathrm{BPP} \subset \Sigma_2</tex>.
<tex>\mathrm{BPP}</tex> можно определить как множество таких языков <tex>L</tex>, что <tex>x \in L \Leftrightarrow \exists</tex> существует «много» таких вероятностных лент <tex>y: </tex>, что <tex>R(x,y)</tex>. <tex>\Sigma_2</tex> определяется как множество <tex>= \{ L \bigm| x \in L \Leftrightarrow \exists y \forall z R(x, y, z)\}</tex>. Таким образом, необходимо уметь записывать «<tex>\exists</tex> «существует много» с помощью кванторов <tex>\exists\forall</tex>.
Рассмотрим язык <tex>G = \{0, 1\}^t</tex> для некоторого <tex>t</tex>. Определим операцию <tex>\oplus</tex> над словами из этого языка как побитовое исключающее или.
Если <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>\mathrm{BPP} = </tex> [[Классы BPPweak и BPPstrong | <tex>\mathrm{BPP_{strong}}</tex>]] следует, что существует [[Вероятностные вычисления. Вероятностная машина Тьюринга | вероятностная машина Тьюринга]] <tex>M</tex>, такая что <tex>P(M(x) = [x \in L]) \geqslant 1 - \frac{1}{2^{p(n)}}</tex>, где <tex>p(n)</tex> некоторый полином, который будет определен позднее. Пусть <tex>M</tex> использует <tex>r(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>-большое.
Если <tex>x \not \in L</tex>, то <tex>P(A_x) = \frac{|A_x|}{2^{r(n)}} \leqslant \frac{1}{2^{p(n)}} \Rightarrow |A_x| \leqslant 2^{r(n) - p(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-маленьким потребуем <tex>2^{r(n) - p(n)} < \frac{2^{r(n)}}{k}</tex>.
Выберем <tex>p(n)</tex> так, чтобы <tex>\frac{r(n)}{p(n)} < 2^{p(n)} - 2</tex> и <tex>k = \lceil \frac{r(n)}{p(n)} \rceil + 1</tex>. Получаем <tex>\frac{r(n)}{p(n)} < k < 2^{p(n)}</tex>, то есть <tex>x \in L \Leftrightarrow A_x</tex> — <tex>k</tex>-большое.
Таким образом, <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \subset G</tex> <tex>\forall y \in G</tex> <tex>\bigvee\limits_{i=1}^{k} y \in g_i \oplus A_x</tex>, то есть <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \subset G</tex> <tex>\forall y \in G</tex> <tex>\bigvee\limits_{i=1}^{k} y \oplus g_i \in A_x</tex>, то есть <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \subset G</tex> <tex>\forall y \in G</tex> <tex>\bigvee\limits_{i=1}^{k} M(x, y \oplus g_i)</tex>, а, значит, <tex>L \in \Sigma_2</tex>, <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2}</tex> и <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}</tex>.
}}
== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы PH, Σ и Π]]
*[[Классы BPPweak и BPPstrong]]
[[Категория: Теория сложности]]
