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

Лемма:

[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]. [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]. [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]

См. также

• Вероятностные вычисления. Вероятностная машина Тьюринга
• Классы PH, Σ и Π
• Классы BPPweak и BPPstrong

Литература

• Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach