Бюрократы, editor, Администраторы
422
правки
Изменения
→Теорема о коллапсе полиномиальной иерархии при совпадении \Sigma_i и \Pi_i
|statement = Если существует <tex>i > 0\colon \Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = PH</tex>.
|proof =
Для доказательства теоремы достаточно показатьпокажем, что <tex>\Sigma_i = \Sigma_{i+1}</tex>. Тогда по и воспользуемся предыдущей теореме <tex>\Sigma_i = PH</tex>теоремой.<br/>
Рассмотрим язык <tex>L \in \Sigma_{i+1}</tex>. Тогда слово <tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{i+1} R(x, y_1 \ldots y_{i+1})</tex>. Обозначим <tex>\forall y_2 \exists y_3 \ldots Q y_{i+1} R(x, y_1 \ldots y_{i+1}) = f(x, y_1)</tex>. Получим язык <tex>L_f = \{ \langle x, y_1 \rangle \colon f(x, y_1) = 1\}</tex>.<br>
Тогда <tex>L_f \in \Pi_i</tex>, и из условия теоремы <tex>L_f \in \Sigma_i</tex>.<br/>
По определению сложностного класса <tex>\Sigma_i \; \exists R_1 \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \exists y_2 \forall y_3 \ldots Q y_{i+1} R_1(\langle x, y_1 \rangle, y_2 \ldots y_{i+1})</tex>. Тогда<tex>x \in L \Leftrightarrow \exists \langle y_1, y_2 \rangle \forall y_3 \ldots Q y_{i+1} R_1(x, \langle y_1, y_2\rangle \ldots y_{i+1})</tex>. Значит, <tex>L \in \Sigma_i</tex>. То есть <tex>\Sigma_i = \Sigma_{i+1}</tex>.
}}
== См. также ==
*[[Классы PH, Σ и Π]]
