205
правок
Изменения
Нет описания правки
{{Лемма
|statement = Если <tex>\Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Pi_i = \Pi_{i+1}</tex>.
|proof = Так как <tex>\Sigma_i = \Sigma_{i+1}</tex>, то любой язык <tex>L \in \Sigma_{i+1}</tex> входит в сложностный класс <tex>\Sigma_i</tex>. Очевидно, что если язык <tex>L \in \Sigma_i</tex>, то <tex>\overline{L} \in \Pi_i</tex>.<br/> Тогда для языка <tex>L</tex> выполнено <tex>\overline{L} \in \Pi_{i+1} \Leftrightarrow L \in \Sigma_{i+1} \Leftrightarrow L \in \Sigma_i \Leftrightarrow \overline{L} \in \Pi_i</tex>
}}
== Теорема о коллапсе полиномиальной иерархии при совпадении <math>\Sigma_i</math> и <math>\Sigma_{i+1}</math> ==
