109
правок
Изменения
м
→Доказательство
<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>\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>M</tex>.
Зафиксируем <tex>x</tex>. Возьмем <tex>k = p(|x|)</tex>. Рассмотрим множество начал длины <tex>mk</tex> вероятностных лент <tex>X</tex>, на которых
машина <tex>M</tex> выдает единицу, то есть <tex>X = \{y \in G \mid M(x,y) = 1\}</tex>.
Из того, что вероятность ошибки не превосходит <tex>\frac1{3k}</tex>, следует:
* <tex>x \in L \Rightarrow rightarrow \frac{|X|}{|G|} \geqslant 1 - \frac1{3k}</tex>* <tex>x \not \in L \Rightarrow rightarrow \frac{|X|}{|G|} \leqslant \frac1{3k}</tex>
Если <tex>x \in L</tex>, то:
