1632
правки
Изменения
м
rollbackEdits.php mass rollback
Рассмотрим язык <tex>G = \{0, 1\}^t</tex> для некоторого <tex>t</tex>. Определим операцию <tex>\oplus</tex> над словами из этого языка как побитовое исключающее или.
Назовем <tex>X</tex>, содержащееся в <tex>G</tex>, <tex>k</tex>-большим, если существует такой набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>, что <tex>\bigcup\limits_{i=1}^{k} g_i \oplus X = GU</tex>. Иначе будем называть <tex>X</tex> — <tex>k</tex>-маленьким.
Если <tex>|X| < \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>x \not \in L</tex>, то <tex>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)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-маленьким потребуем <tex>2^{t(n) - p(n)} < \frac{2^{t(n)}}{k}</tex>.
Выберем <tex>p(n)</tex> так, чтобы <tex>\frac{t(n)}{p(n)} < 2^{p(n)} - </tex> (то есть <tex>c r(n) p(n) < 2^{p(n)}</tex> ) и <tex>k = \lceil \frac{t(n)}{p(n)} \rceil + 1 = c r(n) p(n) + 1</tex>. Получаем <tex>\frac{t(n)}{p(n)} < k < 2^{p(n)}</tex>, то есть <tex>x \in L \Leftrightarrow A_x</tex> — <tex>k</tex>-большое.
Таким образом, <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \subset G</tex> : <tex>\forall y \in G</tex> <tex>\left( \bigvee\limits_{i=1}^{k} y \in g_i \oplus A_x \right) </tex>. Заметив, что <tex>y \in g_i \oplus A_x \Leftrightarrow y \oplus g_i \in A_x \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>.
