Теорема Лаутемана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
Из того, что класс <tex>\mathrm{BPP}</tex> замкнут относительно дополнения и <tex>\mathrm{co}\Sigma_2 = \Pi_2</tex>, следует, что достаточно доказать включение <tex>\mathrm{BPP} \subset \Sigma_2</tex>.
 
Из того, что класс <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</tex> существует «много» таких вероятностных лент <tex>y</tex>, что <tex>R(x,y)</tex>. <tex>\Sigma_2 = \{ L \bigm| x \in L \Leftrightarrow \exists y \forall z R(x, y, z)\}</tex>. Таким образом, необходимо уметь записывать «существует много» с помощью кванторов <tex>\exists\forall</tex>.
+
<tex>\mathrm{BPP}</tex> можно определить как множество таких языков <tex>L</tex>, что <tex>x \in L \Leftrightarrow</tex> существует «много» таких вероятностных лент <tex>y</tex>, что <tex>R(x,y)</tex>. <tex>\mathrm{\Sigma_2}</tex> — множество таких языков <tex>L</tex>, что <tex>x \in L \Leftrightarrow</tex> существует такой <tex>y</tex>, что для любого <tex>z</tex> <tex>R(x, y, z)</tex>. Таким образом, необходимо уметь записывать «существует много» с помощью кванторов <tex>\exists\forall</tex>.
  
 
Рассмотрим язык <tex>G = \{0, 1\}^t</tex> для некоторого <tex>t</tex>. Определим операцию <tex>\oplus</tex> над словами из этого языка как побитовое исключающее или.
 
Рассмотрим язык <tex>G = \{0, 1\}^t</tex> для некоторого <tex>t</tex>. Определим операцию <tex>\oplus</tex> над словами из этого языка как побитовое исключающее или.
Строка 22: Строка 22:
 
Если <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>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} = \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>L \in \mathrm{BPP}</tex>. Из того, что <tex>\mathrm{BPP} = \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</tex>. Возьмем <tex>G = \{0, 1\}^{r(n)}</tex>. Рассмотрим множество <tex>A_x = \{r \in G \bigm| M(x,r) = 1\}</tex>, являющееся событием в вероятностном пространстве <tex>\left( G, 2^{G}, P \right)</tex>, где <tex>P(r) = \frac{1}{|G|} \forall r \in G</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(A_x) = \frac{|A_x|}{2^{r(n)}} \geqslant 1 - \frac{1}{2^{p(n)}} \Rightarrow |A_x| \geqslant 2^{r(n)} \left( 1 - \frac{1}{2^{p(n)}} \right)</tex>. Значит <tex>2^{r(n)} \left( 1 - \frac{|A_x|}{2^{r(n)}} \right)^k \leqslant 2^{r(n) - kp(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-большим потребуем <tex>2^{r(n) - kp(n)} < 1</tex>.
 
Если <tex>x \in L</tex>, то <tex>P(A_x) = \frac{|A_x|}{2^{r(n)}} \geqslant 1 - \frac{1}{2^{p(n)}} \Rightarrow |A_x| \geqslant 2^{r(n)} \left( 1 - \frac{1}{2^{p(n)}} \right)</tex>. Значит <tex>2^{r(n)} \left( 1 - \frac{|A_x|}{2^{r(n)}} \right)^k \leqslant 2^{r(n) - kp(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-большим потребуем <tex>2^{r(n) - kp(n)} < 1</tex>.
Строка 32: Строка 32:
 
Выберем <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>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>.
+
Таким образом, <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>y \in g_i \oplus A_x \Leftrightarrow y \oplus g_i \Leftrightarrow 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>.
 
}}
 
}}
  

Версия 21:59, 3 июня 2012

Теорема

Теорема (Лаутеман):
[math]\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}[/math]
Доказательство:
[math]\triangleright[/math]

Из того, что класс [math]\mathrm{BPP}[/math] замкнут относительно дополнения и [math]\mathrm{co}\Sigma_2 = \Pi_2[/math], следует, что достаточно доказать включение [math]\mathrm{BPP} \subset \Sigma_2[/math].

[math]\mathrm{BPP}[/math] можно определить как множество таких языков [math]L[/math], что [math]x \in L \Leftrightarrow[/math] существует «много» таких вероятностных лент [math]y[/math], что [math]R(x,y)[/math]. [math]\mathrm{\Sigma_2}[/math] — множество таких языков [math]L[/math], что [math]x \in L \Leftrightarrow[/math] существует такой [math]y[/math], что для любого [math]z[/math] [math]R(x, y, z)[/math]. Таким образом, необходимо уметь записывать «существует много» с помощью кванторов [math]\exists\forall[/math].

Рассмотрим язык [math]G = \{0, 1\}^t[/math] для некоторого [math]t[/math]. Определим операцию [math]\oplus[/math] над словами из этого языка как побитовое исключающее или.

Назовем [math]X[/math], содержащееся в [math]G[/math], [math]k[/math]-большим, если существует такой набор [math]\{g_i\}_{i=1}^{k} \subset G[/math], что [math]\bigcup\limits_{i=1}^{k} g_i \oplus X = G[/math]. Иначе будем называть [math]X[/math][math]k[/math]-маленьким.

Если [math]|X| \lt \frac{2^t}{k}[/math], то [math]X[/math] является [math]k[/math]-маленьким. Найдем достаточное условие, при котором [math]X[/math] является [math]k[/math]-большим.

Воспользуемся утверждением, что если вероятность [math]P(x \in A) \gt 0[/math], то существует [math]x[/math] из [math]A[/math]. Для этого выберем случайно набор [math]\{g_i\}_{i=1}^{k} \subset G[/math].

[math]P(\bigcup\limits_{i=1}^{k} g_i \oplus X \not = G) = P(\exists y \not \in \bigcup\limits_{i=1}^{k} g_i \oplus X) = P(\bigvee\limits_{i=1}^{2^t} y_i \not \in \bigcup\limits_{j=1}^{k} g_j \oplus X) \leqslant 2^t P(y \not \in \bigcup\limits_{i=1}^{k} g_i \oplus X) = 2^t P(\bigwedge\limits_{i=1}^{k} y \oplus g_i \not \in X) = 2^t \left(P(y \not \in X)\right)^k = 2^t \left(1 - \frac{|X|}{2^t}\right)^k[/math].

Если [math]2^t\left(1 - \frac{|X|}{2^t}\right)^k \lt 1[/math], то существует такой набор [math]\{g_i\}_{i=1}^{k} \subset G[/math], что [math]\bigcup\limits_{i=1}^{k} g_i \oplus X = G[/math], то есть [math]X[/math][math]k[/math]-большое.

Рассмотрим язык [math]L \in \mathrm{BPP}[/math]. Из того, что [math]\mathrm{BPP} = \mathrm{BPP_{strong}}[/math], следует, что существует вероятностная машина Тьюринга [math]M[/math], такая что [math]P(M(x) = [x \in L]) \geqslant 1 - \frac{1}{2^{p(n)}}[/math], где [math]p(n)[/math] некоторый полином, который будет определен позднее. Пусть [math]M[/math] использует [math]r(n)[/math] бит случайной ленты.

Зафиксируем [math]x[/math]. Возьмем [math]G = \{0, 1\}^{r(n)}[/math]. Рассмотрим множество [math]A_x = \{r \in G \bigm| M(x,r) = 1\}[/math], являющееся событием в вероятностном пространстве [math]\left( G, 2^{G}, P \right)[/math], где [math]P(r) = \frac{1}{|G|} \forall r \in G[/math]. Подберем теперь [math]p(n)[/math] и [math]k[/math] так, чтобы [math]x \in L \Leftrightarrow A_x[/math][math]k[/math]-большое.

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

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

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

Таким образом, [math]x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \subset G[/math] : [math]\forall y \in G[/math] [math]\bigvee\limits_{i=1}^{k} y \in g_i \oplus A_x[/math], [math]y \in g_i \oplus A_x \Leftrightarrow y \oplus g_i \Leftrightarrow M(x, y \oplus g_i)[/math]. Получаем [math]L \in \Sigma_2[/math], [math]\mathrm{BPP} \subset \mathrm{\Sigma_2}[/math] и [math]\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}[/math].
[math]\triangleleft[/math]

См. также