Изменения

{{Лемма| 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' (Sipser–Lautemann theorem или Sipser–Gács–Lautemann theoremx) состоит в том, что класс = [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]] содержится в классах [[Классы Sigma_i и Pi_i|} \subset \mathrm{coBPP}</tex>.#<mathtex>L \Sigma_2in \mathrm{coBPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{BPP}</mathtex> и . Получаем <mathtex>\Pi_2mathrm{coBPP} \subset \mathrm{BPP}</mathtex>]] [[Полиномиальная иерархия | полиномиальной иерархии]].}}

==ДоказательствоТеорема=={{ Теорема| 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 \Leftrightarrow \exists</tex> тогда и только тогда, когда существует «много» таких вероятностных лент <tex>y: R</tex>, что <tex>M(x,y)</tex>, где <tex>M</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга | вероятностная машина Тьюринга]] для <tex>L</tex>. <tex>\mathrm{\Sigma_2}</tex> определяется как — множество таких языков <tex>\{ L \mid </tex>, что <tex>x \in L \Leftrightarrow \exists </tex> тогда и только тогда, когда существует такой <tex>y \forall </tex>, что для любого <tex>z </tex> <tex>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} \subset G</tex> такой, что <tex>\bigcup_bigcup\limits_{i=1}^{k} g_i \oplus X = GU</tex>. Иначе будем называть <tex>X</tex> — <tex>k</tex>-маленьким.

Если <tex>k|X| < |G|\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>\{g_i\}_{i=1}^{k} \subset G</tex>.

Для некотрого <tex>y \in G</tex>:* <tex>P(y \in bigcup\limits_{i=1}^{k} g_i \oplus X\not = G) = P(\exists y \oplus not \in \bigcup\limits_{i=1}^{k} g_i \in oplus X) = P(\fracbigvee\limits_{|X|i=1}^{|G|2^t}</tex>;* <tex>P(y y_i \not \in g_i \oplus X) bigcup\limits_{j= 1 - \frac{|X|}^{|G|k}g_j \oplus X)</tex>;* <tex>\leqslant 2^t P(y \not \in \bigwedge_bigcup\limits_{i=1}^{k} y \not \in g_i \oplus X) = \left(1 - \frac{|X|}{|G|}\right)2^k</tex>;* <tex>t P(\exists y bigwedge\in G \bigwedge_limits_{i=1}^{k} y \oplus g_i \not \in g_i X) = 2^t \left(P(y \not \oplus in X) \right)^k = |G|2^t \left(1 - \frac{|X|}{|G|2^t}\right)^k</tex>.

Если <tex>|G|2^t\left(1 - \frac{|X|}{|G|2^t}\right)^k < 1</tex>, то существует такой набор <tex>\{g_i\}_{i=1}^{k} \subset G</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>MP(m(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Пусть <tex>m</tex>, распознающая этот язык, завершается за использует <tex>pr(|x|n)</tex> шагов бит случайной ленты. По аналогии c [[Классы BPP и PP|доказательством]] <tex>\mathrm{BPP} = \mathrm{BPP_{strong}}</tex>, построим машину <tex>M</tex>, которая запускает <tex>m</tex> достаточное число раз, чтобы получить вероятность ошибки не превосходит<tex>\frac{1}{3p2^{p(|x|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>k G = p\{0, 1\}^{t(|x|n)}</tex>. Рассмотрим множество начал длины <tex>kA_x = \{r \in G \bigm| 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 \frac1{3k}in L</tex>, следует:* то <tex>P(M(x ) = 1) = \in L frac{|A_x|}{2^{t(n)}} \rightarrow geqslant 1 - \frac{|X|1}{2^{p(n)}} \Rightarrow |GA_x|\geqslant 2^{t(n)} \geqslant left( 1 - \frac1frac{1}{2^{3kp(n)}} \right)</tex>;* . Значит <tex>x 2^{t(n)} \not \in L \rightarrow left( 1 - \frac{|XA_x|}{|G|2^{t(n)}} \right)^k \leqslant \frac12^{t(n) - kp(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-большим потребуем <tex>2^{3kt(n) - kp(n)}< 1</tex>.

Если <tex>x \not \in L</tex>, то:* <tex>P(M(x) = 1) = \frac{|XA_x|}{|G|2^{t(n)}} \geqslant leqslant \frac{1 - }{2^{p(n)}} \Rightarrow |A_x| \frac1leqslant 2^{3kt(n) - p(n)}</tex>;* . Чтобы в этом случае <tex>A_x</tex> было бы <tex>1 - \frac{|X|}{|G|} \leqslant \frac1{3k}k</tex>;* -маленьким потребуем <tex>|G|\left2^{t(1 n) - p(n)} < \frac{|X|2^{t(n)}{|G|}\right)^k \leqslant |G| \left(\frac1{3k}\right)^k = \left(\frac2{3k}\right)^k < 1</tex>, что влечет за собой то, что <tex>X</tex> большой.

Если Выберем <tex>p(n)</tex> так, чтобы <tex>x \not \in Lfrac{t(n)}{p(n)} < 2^{p(n)}</tex>, (то есть <tex>c r(n) p(n) < 2^{p(n)}</tex>) и <tex>k = \lceil \frac{|X|t(n)}{|G|p(n)} \leqslant rceil + 1 = c r(n) p(n) + 1</tex>. Получаем <tex>\frac1frac{t(n)}{p(n)} < k < 2^{3kp(n)} < /tex>, то есть <tex>x \in L \frac1kLeftrightarrow A_x</tex>, а, следовательно, — <tex>Xk</tex> не является большим-большое.

Таким образом, <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k, g_1, g_2, } \dots, g_k subset G</tex> : <tex>\forall y \bigvee_in G</tex> <tex>\left( \bigvee\limits_{i=1}^{mk} y \in g_i \oplus XA_x \right) </tex>. Заметив, то естьчто <tex>x y \in L g_i \oplus A_x \Leftrightarrow y \exists k, g_1, g_2, oplus g_i \dots, g_k in A_x \forall y \bigvee_{i=1}^{m} 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]  [[Категория: Теория сложности]]