Теорема Лаутемана

2014-06-05T05:37:43Z

80.79.246.42:

{{Лемма
| 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} = \mathrm{\Pi_2}</tex>, следует, что достаточно доказать включение <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2}</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 = \{0, 1\}^t</tex> для некоторого <tex>t</tex>. Определим операцию <tex>\oplus</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>|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>\{g_i\}_{i=1}^{k} \subset 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>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>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>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>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 \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>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 \{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>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы PH, Σ и Π]]
*[[Классы BPPweak и BPPstrong]]

== Литература ==
* ''Sanjeev Arora, Boaz Barak''. [http://www.cs.princeton.edu/theory/complexity Computational Complexity: A Modern Approach]

[[Категория: Теория сложности]]

Викиконспекты - Вклад участника [ru]

Теорема Лаутемана