Бюрократы, editor, Администраторы
422
правки
Изменения
mathrm
== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Sigma_{i+1}</tex> ==
{{Теорема
|statement = Если существует <tex>i \colon \Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.
|proof = Для доказательства теоремы достаточно показать, что если такое <tex>i</tex> существует, то <tex>\forall j > i</tex> верно, что <tex>\Sigma_i = \Sigma_j</tex>.<br/>
Докажем по индукции.<br/>
== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Pi_i</tex> ==
{{Теорема
|statement = Если существует <tex>i > 0\colon \Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.
|proof =
Для доказательства покажем, что <tex>\Sigma_i = \Sigma_{i+1}</tex>, и воспользуемся предыдущей теоремой.
