205
правок
Изменения
м
→Теорема о коллапсе полиномиальной иерархии при совпадении \Sigma_i и \Pi_i
== Теорема о коллапсе полиномиальной иерархии при совпадении <math>\Sigma_i</math> и <math>\Pi_i</math> ==
{{Теорема|statement === Утверждение теоремы ===Если <tex>\Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = PH</tex>. === Доказательство ==|proof =
Доказательство аналогично доказательству предыдущей теоремы. Мы снова будем удалять квантор из формулы и получим, что если можно удалить один квантор, то можно удалить их все.
Значит, <tex>L \in \Sigma_i</tex>, что и требовалось доказать.
}}
