Бюрократы, editor, Администраторы
422
правки
Изменения
Лемма
{{Лемма
|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_Pi_{i+1}</tex> входит в сложностный класс <tex>\Sigma_i</tex>. Очевидно, что если язык <tex>L \in \Sigma_i</tex>, то <tex>Leftrightarrow \overline{L} \in \Pi_i</tex>.<br/> Тогда для языка <tex>L</tex> выполнено <tex>\overline{L} \in \Pi_Sigma_{i+1} \Leftrightarrow L \in \Sigma_overline{i+1L} \Leftrightarrow L \in \Sigma_i \Leftrightarrow \overline{L} \in \Pi_i</tex>. То есть <tex>\Pi_i = \Pi_{i+1}</tex>.
}}
