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

Формулировка

Теорема Лаутемана (Sipser–Lautemann theorem или Sipser–Gács–Lautemann theorem) утверждает, что класс BPP содержится в классах [math]\Sigma_2[/math] и [math]\Pi_2[/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 \exists[/math] «много» вероятностных лент [math]y: R(x,y)[/math]. [math]\Sigma_2[/math] определяется, как множество [math]\{ L \mid x \in L \Leftrightarrow \exists y \forall z R(x, y, z)\}[/math]. Таким образом, необходимо уметь записывать «много» с помощью квантора [math]\forall[/math].

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

Назовем [math]X[/math], содержащееся в [math]G[/math] большим, если существует набор [math]g_1, g_2, \dots g_k[/math] (значение [math]k[/math] тоже будет получено позже) такой, что [math]\bigcup_{i=1}^{k} g_i \oplus X = G[/math].

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

Выберем случауно набор [math]\{g_i\}[/math].

Для некотрого [math]y \in G[/math]:

• [math]P(y \in g_i \oplus X) = P(y \oplus g_i \in X) = \frac{|X|}{|G|}[/math],
• [math]P(y \not \in g_i \oplus X) = 1 - \frac{|X|}{|G|}[/math]
• [math]P(\bigwedge_{i=1}^{k} y \not \in g_i \oplus X) = \left(1 - \frac{|X|}{|G|}\right)^k[/math]
• [math]P(\exists y \in G \bigwedge_{i=1}^{k} y \not \in g_i \oplus X) = |G|\left(1 - \frac{|X|}{|G|}\right)^k[/math]

Если [math]|G|\left(1 - \frac{|X|}{|G|}\right)^k \lt 1[/math], то существует набор [math]\{g_i\}[/math], что для любого [math]y[/math] [math]\bigwedge_{i=1}^{k} y \not \in g_i \oplus X[/math], а из этого следует, что [math]X[/math] большой.

Рассмотрим язык [math]L \in \mathrm{BPP}[/math].

[math]X_x = \{y \mid M(x,y) = 1\}[/math]

[math]x \in L \Rightarrow \frac{|X_x|}{|G|} \geqslant 1 - \varepsilon[/math]

[math]x \not \in L \Rightarrow \frac{|X_x|}{|G|} \leqslant \varepsilon[/math]