205
правок
Изменения
м
→Теорема о коллапсе полиномиальной иерархии при совпадении \Sigma_i и \Sigma_{i+1}
Тогда получим язык <tex>L_f = \{\langle x, y_1\rangle \colon f(x, y_1) = 1\}</tex>.<br/>
Заметим, что <tex>L_f \in \Pi_{n+1}</tex> и из вышедоказанной леммы следует, что <tex>L_f \in \Pi_n</tex>.<br/>
Из определения сложностного класса <tex>\Pi_n</tex> получаем, что <tex>\exists R_{L_f}^{n} \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \forall y_2 \exists y_3 \ldots Q y_{n+1} R_{L_f}^{n}(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>. Следовательно, <tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+1} R_L^{n+1}(x, y_1, y_2 \ldots y_{n+1})</tex>. <tex>R_L^{n+1}(x, y_1, y_2 \ldots y_{n+1})</tex> '''return''' <tex>R_{L_f}^{n}(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>. То есть язык <tex>L \in \Sigma_{n+1}</tex>.
}}
