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