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