Бюрократы, editor, Администраторы
422
правки
Изменения
→Теорема о коллапсе полиномиальной иерархии при совпадении \Sigma_i и \Pi_i: i=0
<tex>R_L^i(x, \langle y_1, y_2\rangle, y_3 \ldots, y_{i+1})</tex>
'''return''' <tex>R_{L_f}^i(\langle x, y_1\rangle, y_2, y_3 \ldots y_{i+1})</tex>
Значит, <tex>L \in \Sigma_i</tex>.<br/>Заметим, что при <tex>i = 0</tex> теорема, скорее всего, неверна. Так как если взять язык <tex>L \in \Sigma_1</tex> и выполнить все шаги доказательства, то на выходе получится язык из <tex>\Sigma_1</tex>, а не из <tex>\Sigma_0</tex>.
}}
Заметим, что <tex>\Sigma_0 = \Pi_0 = \mathrm{P}</tex>, а потому формулировка теоремы не имеет смысла при <tex>i = 0</tex>.
== См. также ==
*[[Классы PH, Σ и Π]]
