Изменения

<tex>\Sigma_{i} = \{L\bigm|\exists R(x,y_{1},\cdots,y_{i}) \in \mathrm{P}, p </tex> {{- --}} <tex>poly : \forall x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \exists y_{3} \cdots Q y_{i} : \forall j |y_{j}|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\},</tex><br/>где <tex>L</tex> - — формальный язык <tex>,Q = \exists</tex> для <tex>i = 2k-1,</tex> <tex>Q = \forall</tex> для <tex>i = 2k</tex>.

<tex>\Pi_{i} = \{L\bigm|\exists R(x, y_{1},\cdots,y_{i}) \in \mathrm{P}, p </tex> {{- --}} <tex>poly : \forall x \in L \Leftrightarrow \forall y_{1} \exists y_{2} \forall y_{3} \cdots Q y_{i} : \forall j |y_{j}|~\le~p(|x|), R(x, y_{1}, \cdots, y_{i}) \},</tex><br/>где <tex>L</tex> - — формальный язык <tex>,Q = \forall</tex> для <tex>i = 2k - 1,</tex> <tex>Q = \exists</tex> для <tex>i = 2k</tex>.

==Взаимоотношения Соотношения между классами <tex>\Sigma_{i}</tex> Σ и <tex>\Pi_{i}</tex>Π ==

|statement = <tex>\Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>.|proof = Пусть <tex>\left]L \in \Sigma_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i}), \forall j |y_{j}| \right.le poly(|x|)</tex>.<br/>Проверим, что <tex>? L \in \Sigma_{i+1} \Leftrightarrow \exists R' : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} \bar{Q} y_{i+1} : R'(x,y_{1},\cdots,y_{i},y_{i+1})</tex>.

return <tex>R(x,y_{1},\cdots,y_{i})</tex>;

Проверим, что <tex>? L \in \Pi_{i+1} \Leftrightarrow \exists R'' : x \in L \Leftrightarrow \forall y_{0} \exists y_{1} \cdots Q y_{i} : R''(x,y_{0},y_{1},\cdots,y_{i})</tex>.

return <tex>R(x,y_{1},\cdots,y_{i})</tex>;

Т.о.Таким образом, <tex>\Sigma_{i} \subset \Sigma_{i+1}, \Sigma_{i} \subset \Pi_{i+1} \Rightarrow \Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>.

|statement = <tex>\Pi_Sigma_{i} = \subset \Sigma_mathrm{i+1} \cap co\Pi_{i+1}}</tex>.|proof = <tex>\left]L \in mathrm{co\Pi_{i} } = \{L \Rightarrow bigm| \exists R (x,y_{1},\cdots,y_{i}) \in \mathrm{P}, p</tex> {{---}} <tex>poly: x \in L \Leftrightarrow \exists y_{1} \forall y_{12} \cdots Q y_{i} : \forall j |y_j|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\right}.</tex><br/>Из самого выражения для <tex>? L \in mathrm{co\Pi_{i+1} }</tex> очевидно равенство.}} == Пример Σ и Π-полных задач =={{Определение|definition = Задачей <tex>\Leftrightarrow mathrm{QBF^{\Sigma}_{k}}</tex> называется объединение удовлетворимых булевых формул с <tex>k</tex> изменениями кванторов, где первым квантором является <tex>\exists R' : x </tex>.<br/><tex>\mathrm{QBF^{\Sigma}_{k}} = \{\phi \in L bigm| \Leftrightarrow exists X_{1} \forall y_X_{2} \exists X_{3} \cdots : \phi(X_{1} \cdots Q y_X_{k})\}</tex>,<br/>где <tex>X_{i} </tex> {{---}} попарно непересекающиеся множества аргументов <tex>\barphi</tex>.}}<tex>\mathrm{QBF^{\Sigma}_{k}}</tex> {{Q---}} <tex>\mathrm{\Sigma_{k}}</tex>-полная задача (доказательство аналогично доказательству [[Теорема Бермана — Форчуна|coNP-полноты TAUT]]). {{Определение|definition = Задачей <tex>\mathrm{QBF^{\Pi}_{k}}</tex> называется объединение удовлетворимых булевых формул с <tex>k</tex> изменениями кванторов, где первым квантором является <tex>\forall</tex>.<br/><tex>\mathrm{QBF^{\Pi}_{k}} y_= \{\phi \bigm| \forall X_{i+1} \exists X_{2} \forall X_{3} \cdots : R'\phi(x,y_X_{1},\cdotsX_{k})\}</tex>,y_<br/>где <tex>X_{i}</tex> {{---}} попарно непересекающиеся множества аргументов <tex>\phi</tex>.}}Аналогично предыдущей,y_<tex>\mathrm{QBF^{\Pi}_{k}}</tex> {{---}} <tex>\mathrm{\Pi_{k}}</tex>-полная задача. == Класс PH =={{Определение|definition =<tex>\mathrm{PH} = {\bigcup \atop {i \in \mathbb{N}}} \Sigma_{i+1})</tex>.<br/>}}Замечание: иногда удобнее пользоваться альтернативными определениями <tex>\mathrm{PH}<br/tex>. Например: * <tex>R'(x,y_\mathrm{PH} = {\bigcup \atop {i \in \mathbb{1N}}},\cdots,y_Pi_{i+1})</tex> {,<br/> return * <tex>R\mathrm{PH} = {\bigcup \atop {i \in \mathbb{N}}} (x,y_\Sigma_{1i},\cdots,y_cup \Pi_{i})</tex>. {{Теорема |statement = <tex>\mathrm{PH}\subset \mathrm{PS}</tex>.|proof = Пусть <tex>? L \in \Sigma_{i+1} \Leftrightarrow Rightarrow \exists R'' : x \in L \Leftrightarrow \exists y_{0} \forall y_{1} \cdots Q y_{i} : R''(x,y_{01},\cdots,y_{1i}),\cdots,forall j |y_{ij}| \le poly(|x|)</tex>.<br/> То есть, для перебора всех возможных значений <tex>R''(x,y_{0},y_{1j}</tex> потребуется не более,чем <tex>i \cdots,y_{i}cdot poly(|x|)</tex> { return памяти. Заметим, что <tex>Ri \cdot poly(|x,y_{1},\cdots,y_{i}|)</tex>тоже полином. }Т.о.Таким образом, для любого формального языка из <tex>\Pi_mathrm{i} \subset \Sigma_{i+1PH}</tex> существует программа, разрешающая его на полиномиальной памяти. То есть, любой формальный язык из <tex>\Pi_mathrm{iPH} </tex> принадлежит <tex>\subset \Pi_mathrm{i+1} \Rightarrow \Pi_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1PS}</tex>.