109
правок
Изменения
м
→Доказательство
Из того, что класс <tex>\mathrm{BPP}</tex> замкнут относительно дополнения и <tex>\mathrm{co}\Sigma_2 = \Pi_2</tex> следует, что достаточно доказать включение <tex>\mathrm{BPP} \subset \Sigma_2</tex>.
<tex>\mathrm{BPP}</tex> можно определить, как множество таких языков <tex>L</tex>, что <tex>x \in L \Leftrightarrow \exists</tex> «много» вероятностных лент <tex>y: R(x,y)</tex>. <tex>\Sigma_2</tex> определяется, как множество <tex>\{ L \mid x \in L \Leftrightarrow \exists y \forall z R(x, y, z)\}</tex>. Таким образом, необходимо уметь записывать <tex>\exists</tex> «много» с помощью кванторов <tex>\exists\forall</tex>.
Рассмотрим язык <tex>G</tex> всех слов длины <tex>k</tex> над алфавитом <tex>\{0, 1\}</tex>, для некоторого <tex>k</tex>, значение которого будет получено позже. Определим операцию <tex>\oplus</tex> над славами словами из этого языка, как побитовое исключающее или.
Назовем <tex>X</tex>, содержащееся в <tex>G</tex> , большим, если существует набор <tex>g_1, g_2, \dots g_k</tex> такой, что <tex>\bigcup_{i=1}^{k} g_i \oplus X = G</tex>.
Если <tex>k|X| < |G|</tex>, то <tex>X</tex> точное точно не является большим. Найдем достаточное условие, при котором <tex>X</tex> большой.
Воспользуемся утверждением, что если вероятность <tex>P(x \in A) > 0</tex>, то существует <tex>x</tex> из <tex>A</tex>. Для этого
Для некотрого <tex>y \in G</tex>:
* <tex>P(y \in g_i \oplus X) = P(y \oplus g_i \in X) = \frac{|X|}{|G|}</tex>,;* <tex>P(y \not \in g_i \oplus X) = 1 - \frac{|X|}{|G|}</tex>;* <tex>P(\bigwedge_{i=1}^{k} y \not \in g_i \oplus X) = \left(1 - \frac{|X|}{|G|}\right)^k</tex>;* <tex>P(\exists y \in G \bigwedge_{i=1}^{k} y \not \in g_i \oplus X) = |G|\left(1 - \frac{|X|}{|G|}\right)^k</tex>.
Если <tex>|G|\left(1 - \frac{|X|}{|G|}\right)^k < 1</tex>, то существует набор <tex>\{g_i\}</tex>, что для любого <tex>y</tex> <tex>\bigwedge_{i=1}^{k} y \not \in g_i \oplus X</tex>, а из этого следует, что <tex>X</tex> большой.
Рассмотрим язык <tex>L \in \mathrm{BPP}</tex>. Не уменьшая общности, можем считать, что программа <tex>M</tex>, распознающая этот язык, завершается за <tex>p(|x|)</tex> шагов и вероятность ошибки не превосходит
<tex>\frac{1}{3p(|x|)}</tex>, это следует из того, что если запускать программу несколько раз, то время работы растет линейно, а вероятность ошибки
экспоненциально уменьшается. Пусть его распознает машина <tex>M</tex>.
Зафиксируем <tex>x</tex>. Возьмем <tex>k = p(|x|)</tex>. Рассмотрим множество начал длины <tex>k</tex> вероятностных лент <tex>X</tex>, на которых
Из того, что вероятность ошибки не превосходит <tex>\frac1{3k}</tex>, следует:
* <tex>x \in L \rightarrow \frac{|X|}{|G|} \geqslant 1 - \frac1{3k}</tex>;* <tex>x \not \in L \rightarrow \frac{|X|}{|G|} \leqslant \frac1{3k}</tex>.
Если <tex>x \in L</tex>, то:
