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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
м (rollbackEdits.php mass rollback)
 
(не показано 25 промежуточных версий 4 участников)
Строка 1: Строка 1:
==Формулировка==
+
{{Лемма
Утверждение '''теоремы Лаутемана''' (Sipser–Lautemann theorem или Sipser–Gács–Lautemann theorem) состоит в том, что класс [[Класс BPP | BPP]] содержится в классах [[Классы Sigma_i и Pi_i|<math>\Sigma_2</math> и <math>\Pi_2</math>]] [[Полиномиальная иерархия | полиномиальной иерархии]].
+
| statement = <tex>\mathrm{BPP} = \mathrm{coBPP}</tex>
 +
| proof =
 +
Рассмотрим <tex>L \in \mathrm{BPP}</tex>. Существует такая программа <tex>p</tex>, что <tex>P(p(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Покажем, что <tex>\overline{L} \in \mathrm{BPP}</tex>. Для этого рассмотрим следующую программу:
 +
<tex>p'(x):</tex>
 +
    <tex>return (1 - p(x));</tex>
 +
<tex>P(p'(x) = [x \in \overline{L}]) = P(p(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Таким образом <tex>\overline{L} \in \mathrm{BPP}</tex>.
 +
#<tex>L \in \mathrm{BPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{coBPP}</tex>. Получаем <tex>\mathrm{BPP} \subset \mathrm{coBPP}</tex>.
 +
#<tex>L \in \mathrm{coBPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{BPP}</tex>. Получаем <tex>\mathrm{coBPP} \subset \mathrm{BPP}</tex>.
 +
}}
  
==Доказательство==
+
==Теорема==
 +
{{ Теорема
 +
| about = Лаутеман
 +
| statement = <tex>\mathrm{BPP} \subset \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>\mathrm{co\Sigma_2} = \mathrm{\Pi_2}</tex>, следует, что достаточно доказать включение <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2}</tex>.
  
<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>\mathrm{BPP}</tex> можно определить как множество таких языков <tex>L</tex>, что <tex>x \in L</tex> тогда и только тогда, когда существует «много» таких вероятностных лент <tex>y</tex>, что <tex>M(x,y)</tex>, где <tex>M</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга | вероятностная машина Тьюринга]] для <tex>L</tex>. <tex>\mathrm{\Sigma_2}</tex> множество таких языков <tex>L</tex>, что <tex>x \in L</tex> тогда и только тогда, когда существует такой <tex>y</tex>, что для любого <tex>z</tex> <tex>R(x, y, z)</tex>. Таким образом, необходимо уметь записывать «существует много» с помощью кванторов <tex>\exists</tex>, <tex>\forall</tex>.
  
Рассмотрим язык <tex>G</tex> всех слов длины <tex>k</tex> над алфавитом <tex>\{0, 1\}</tex> для некоторого <tex>k</tex>, значение которого будет получено позже. Определим операцию <tex>\oplus</tex> над словами из этого языка как побитовое исключающее или.
+
Рассмотрим язык <tex>G = \{0, 1\}^t</tex> для некоторого <tex>t</tex>. Определим операцию <tex>\oplus</tex> над словами из этого языка как побитовое исключающее или.
  
Назовем <tex>X</tex>, содержащееся в <tex>G</tex>, большим, если существует набор <tex>g_1, g_2, \dots g_k</tex> такой, что <tex>\bigcup_{i=1}^{k} g_i \oplus X = G</tex>.
+
Назовем <tex>X</tex>, содержащееся в <tex>G</tex>, <tex>k</tex>-большим, если существует такой набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>, что <tex>\bigcup\limits_{i=1}^{k} g_i \oplus X = U</tex>. Иначе будем называть <tex>X</tex> — <tex>k</tex>-маленьким.
  
Если <tex>k|X| < |G|</tex>, то <tex>X</tex> точно не является большим. Найдем достаточное условие, при котором <tex>X</tex> большой.
+
Если <tex>|X| < \frac{2^t}{k}</tex>, то <tex>X</tex> является <tex>k</tex>-маленьким (так как <tex>k</tex> копий <tex>X</tex> не смогут покрыть <tex>G</tex>). Найдем достаточное условие, при котором <tex>X</tex> является <tex>k</tex>-большим.
  
 
Воспользуемся утверждением, что если вероятность <tex>P(x \in A) > 0</tex>, то существует <tex>x</tex> из <tex>A</tex>. Для этого  
 
Воспользуемся утверждением, что если вероятность <tex>P(x \in A) > 0</tex>, то существует <tex>x</tex> из <tex>A</tex>. Для этого  
выберем случайно набор <tex>\{g_i\}</tex>.
+
выберем случайно набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>.
  
Для некотрого <tex>y \in G</tex>:
+
<tex>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)</tex> <tex>\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</tex>.
* <tex>P(y \in g_i \oplus X) = P(y \oplus g_i \in X) = \frac{|X|}{|G|}</tex>;
 
* <tex>P(y \not \in g_i \oplus X) = 1 - \frac{|X|}{|G|}</tex>;
 
* <tex>P(\bigwedge_{i=1}^{k} y \not \in g_i \oplus X) = \left(1 - \frac{|X|}{|G|}\right)^k</tex>;
 
* <tex>P(\exists y \in G \bigwedge_{i=1}^{k} y \not \in g_i \oplus X) = |G|\left(1 - \frac{|X|}{|G|}\right)^k</tex>.
 
  
Если <tex>|G|\left(1 - \frac{|X|}{|G|}\right)^k < 1</tex>, то существует набор <tex>\{g_i\}</tex>, что для любого <tex>y</tex> выполнено <tex>\bigvee_{i=1}^{k} y \in g_i \oplus X</tex>, а из этого следует, что <tex>X</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>M</tex>, распознающая этот язык, завершается за <tex>p(|x|)</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>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>\frac{1}{3p(|x|)}</tex>, это следует из того, что если запускать программу несколько раз, то время работы растет линейно, а вероятность ошибки
 
экспоненциально уменьшается.
 
  
Зафиксируем <tex>x</tex>. Возьмем <tex>k = p(|x|)</tex>. Рассмотрим множество начал длины <tex>k</tex> вероятностных лент <tex>X</tex>, на которых
+
Зафиксируем <tex>x</tex>. Возьмем <tex>G = \{0, 1\}^{t(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>M</tex> выдает единицу, то есть <tex>X = \{y \in G \mid M(x,y) = 1\}</tex>.
 
  
Из того, что вероятность ошибки не превосходит <tex>\frac1{3k}</tex>, следует:
+
Если <tex>x \in L</tex>, то <tex>P(M(x) = 1) = \frac{|A_x|}{2^{t(n)}} \geqslant 1 - \frac{1}{2^{p(n)}} \Rightarrow |A_x| \geqslant 2^{t(n)} \left( 1 - \frac{1}{2^{p(n)}} \right)</tex>. Значит <tex>2^{t(n)} \left( 1 - \frac{|A_x|}{2^{t(n)}} \right)^k \leqslant 2^{t(n) - kp(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-большим потребуем <tex>2^{t(n) - kp(n)} < 1</tex>.
* <tex>x \in L \rightarrow \frac{|X|}{|G|} \geqslant 1 - \frac1{3k}</tex>;
 
* <tex>x \not \in L \rightarrow \frac{|X|}{|G|} \leqslant \frac1{3k}</tex>.
 
  
Если <tex>x \in L</tex>, то:
+
Если <tex>x \not \in L</tex>, то <tex>P(M(x) = 1) = \frac{|A_x|}{2^{t(n)}} \leqslant \frac{1}{2^{p(n)}} \Rightarrow |A_x| \leqslant 2^{t(n) - p(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-маленьким потребуем <tex>2^{t(n) - p(n)} < \frac{2^{t(n)}}{k}</tex>.
* <tex>\frac{|X|}{|G|} \geqslant 1 - \frac1{3k}</tex>;
 
* <tex>1 - \frac{|X|}{|G|} \leqslant \frac1{3k}</tex>;
 
* <tex>|G|\left(1 - \frac{|X|}{|G|}\right)^k \leqslant |G| \left(\frac1{3k}\right)^k = \left(\frac2{3k}\right)^k < 1</tex>, что влечет за собой то, что <tex>X</tex> большой.
 
  
Если <tex>x \not \in L</tex>, то <tex>\frac{|X|}{|G|} \leqslant \frac1{3k} < \frac1k</tex>, а, следовательно, <tex>X</tex> не является большим.
+
Выберем <tex>p(n)</tex> так, чтобы <tex>\frac{t(n)}{p(n)} < 2^{p(n)}</tex> (то есть <tex>c r(n) p(n) < 2^{p(n)}</tex>) и <tex>k = \lceil \frac{t(n)}{p(n)} \rceil + 1 = c r(n) p(n) + 1</tex>. Получаем <tex>\frac{t(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 k, g_1, g_2, \dots, g_k \forall y \bigvee_{i=1}^{k} y \in g_i \oplus X</tex>, то есть <tex>x \in L \Leftrightarrow \exists k, g_1, g_2, \dots, g_k \forall y \bigvee_{i=1}^{k} y \oplus g_i \in X</tex>, то есть
+
Таким образом, <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \subset G</tex> : <tex>\forall y \in G</tex> <tex>\left( \bigvee\limits_{i=1}^{k} y \in g_i \oplus A_x \right) </tex>. Заметив, что <tex>y \in g_i \oplus A_x \Leftrightarrow y \oplus g_i \in A_x \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>.
<tex>x \in L \Leftrightarrow \exists k, g_1, g_2, \dots, g_k \forall y \bigvee_{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>, что и требовалось доказать.
+
 
 +
== См. также ==
 +
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 +
*[[Классы PH, Σ и Π]]
 +
*[[Классы BPPweak и BPPstrong]]
 +
 
 +
== Литература ==
 +
* ''Sanjeev Arora, Boaz Barak''. [http://www.cs.princeton.edu/theory/complexity Computational Complexity: A Modern Approach]
 +
 
 +
 
 +
[[Категория: Теория сложности]]

Текущая версия на 19:28, 4 сентября 2022

Лемма:
[math]\mathrm{BPP} = \mathrm{coBPP}[/math]
Доказательство:
[math]\triangleright[/math]

Рассмотрим [math]L \in \mathrm{BPP}[/math]. Существует такая программа [math]p[/math], что [math]P(p(x) = [x \in L]) \geqslant \frac{2}{3}[/math]. Покажем, что [math]\overline{L} \in \mathrm{BPP}[/math]. Для этого рассмотрим следующую программу:

[math]p'(x):[/math]
    [math]return (1 - p(x));[/math]

[math]P(p'(x) = [x \in \overline{L}]) = P(p(x) = [x \in L]) \geqslant \frac{2}{3}[/math]. Таким образом [math]\overline{L} \in \mathrm{BPP}[/math].

  1. [math]L \in \mathrm{BPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{coBPP}[/math]. Получаем [math]\mathrm{BPP} \subset \mathrm{coBPP}[/math].
  2. [math]L \in \mathrm{coBPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{BPP}[/math]. Получаем [math]\mathrm{coBPP} \subset \mathrm{BPP}[/math].
[math]\triangleleft[/math]

Теорема

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

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

[math]\mathrm{BPP}[/math] можно определить как множество таких языков [math]L[/math], что [math]x \in L[/math] тогда и только тогда, когда существует «много» таких вероятностных лент [math]y[/math], что [math]M(x,y)[/math], где [math]M[/math] вероятностная машина Тьюринга для [math]L[/math]. [math]\mathrm{\Sigma_2}[/math] — множество таких языков [math]L[/math], что [math]x \in L[/math] тогда и только тогда, когда существует такой [math]y[/math], что для любого [math]z[/math] [math]R(x, y, z)[/math]. Таким образом, необходимо уметь записывать «существует много» с помощью кванторов [math]\exists[/math], [math]\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 = U[/math]. Иначе будем называть [math]X[/math][math]k[/math]-маленьким.

Если [math]|X| \lt \frac{2^t}{k}[/math], то [math]X[/math] является [math]k[/math]-маленьким (так как [math]k[/math] копий [math]X[/math] не смогут покрыть [math]G[/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)[/math] [math]\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]m[/math], такая что [math]P(m(x) = [x \in L]) \geqslant \frac{2}{3}[/math]. Пусть [math]m[/math] использует [math]r(n)[/math] бит случайной ленты. По аналогии c доказательством [math]\mathrm{BPP} = \mathrm{BPP_{strong}}[/math], построим машину [math]M[/math], которая запускает [math]m[/math] достаточное число раз, чтобы получить вероятность ошибки [math]\frac{1}{2^{p(n)}}[/math], где [math]p(n)[/math] это некоторый полином, который будет определён позднее. Будет достаточно [math]c p(n)^2[/math] запусков. Соответственно, [math]M[/math] использует [math]t(n) = c r(n) p(n)^2[/math] бит случайной ленты, [math]P(M(x) = [x \in L]) \geqslant 1 - \frac{1}{2^{p(n)}}[/math].

Зафиксируем [math]x[/math]. Возьмем [math]G = \{0, 1\}^{t(n)}[/math]. Рассмотрим множество [math]A_x = \{r \in G \bigm| M(x,r) = 1\}[/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(M(x) = 1) = \frac{|A_x|}{2^{t(n)}} \geqslant 1 - \frac{1}{2^{p(n)}} \Rightarrow |A_x| \geqslant 2^{t(n)} \left( 1 - \frac{1}{2^{p(n)}} \right)[/math]. Значит [math]2^{t(n)} \left( 1 - \frac{|A_x|}{2^{t(n)}} \right)^k \leqslant 2^{t(n) - kp(n)}[/math]. Чтобы в этом случае [math]A_x[/math] было бы [math]k[/math]-большим потребуем [math]2^{t(n) - kp(n)} \lt 1[/math].

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

Выберем [math]p(n)[/math] так, чтобы [math]\frac{t(n)}{p(n)} \lt 2^{p(n)}[/math] (то есть [math]c r(n) p(n) \lt 2^{p(n)}[/math]) и [math]k = \lceil \frac{t(n)}{p(n)} \rceil + 1 = c r(n) p(n) + 1[/math]. Получаем [math]\frac{t(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]\left( \bigvee\limits_{i=1}^{k} y \in g_i \oplus A_x \right) [/math]. Заметив, что [math]y \in g_i \oplus A_x \Leftrightarrow y \oplus g_i \in A_x \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]

См. также

Литература