205
правок
Изменения
м
→Теорема о коллапсе полиномиальной иерархии при совпадении \Sigma_i и \Sigma_{i+1}
== Теорема о коллапсе полиномиальной иерархии при совпадении <math>\Sigma_i</math> и <math>\Sigma_{i+1}</math> ==
{{Теорема|statement === Утверждение теоремы ===Если <tex>\Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Sigma_i = PH</tex>. === Доказательство ==|proof =Из <tex>\Sigma_i = \Sigma_{i+1}</tex> очевидным образом следует <tex>\Pi_i = \Pi_{i+1}</tex>.
Докажем, что если <tex>\Sigma_n = \Sigma_{n+1}</tex>, то <tex>\Sigma_n = \Sigma_{n+2}</tex>.
Получается, что <tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+1} R_1(\overline{x, y_1}, y_2 \ldots y_{n+1})</tex>, откуда следует <tex>L \in \Sigma_{n+2} \Rightarrow L \in \Sigma_{n+1}</tex>, что и требовалось доказать.
}}
== Теорема о коллапсе полиномиальной иерархии при совпадении <math>\Sigma_i</math> и <math>\Pi_i</math> ==
