Изменения

Утверждение '''теоремы Лаутемана''' (Sipser–Lautemann theorem или Sipser–Gács–Lautemann theorem) состоит в том, что класс [[Класс BPP | BPP]] содержится в классах [[Классы Sigma_i и Pi_i|<math>\Sigma_2</math> и <math>\Pi_2</math>]] [[Полиномиальная иерархия | полиномиальной иерархии]].

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

<tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \forall y \bigvee\limits_{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>, что и требовалось доказать.