Изменения

<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>.

== Взаимоотношения Соотношения между классами Σ и Π ==

|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}| \le poly(|x|)\right.</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} } = \Rightarrow \exists R : x \in {L \Leftrightarrow bigm| \forall y_{1} \cdots Q y_{i} : exists R(x,y_{1},\cdots,y_{i}), \forall j |y_in \mathrm{jP}| \le poly(|x|)\right., p</tex><br/>{{---}} <tex>? L \in \Pi_{i+1} \Leftrightarrow \exists R' poly: x \in L \Leftrightarrow \forall exists y_{1} \cdots Q forall y_{i2} \bar{cdots Q} y_{i+1} : \forall j |y_j|~\le~p(|x|), R'(x,y_{1},\cdots,y_{i},y_{i+1)\}).</tex><br/> Из самого выражения для <tex>R'(x,y_\mathrm{1},co\cdots,y_Pi_{i+1})}</tex> очевидно равенство.}} == Пример Σ и Π-полных задач =={{Определение return |definition = Задачей <tex>R(x,y_\mathrm{QBF^{\Sigma}_{1k}}</tex> называется объединение удовлетворимых булевых формул с <tex>k</tex> изменениями кванторов,где первым квантором является <tex>\cdots,y_{i})exists</tex> }.<br/><tex>? L \in mathrm{QBF^{\Sigma_Sigma}_{i+1k}} = \Leftrightarrow \exists R'' : x {\in L phi \Leftrightarrow bigm| \exists y_X_{01} \forall y_X_{12} \cdots Q y_exists X_{i3} \cdots : R''\phi(x,y_{0},y_X_{1},\cdots,y_X_{ik})\}</tex>,<br/> где <tex>R''(x,y_{0},y_{1},\cdots,y_X_{i})</tex> { return <tex>R(x,y_{1---},\cdots,y_{i})</tex> }Т.о., попарно непересекающиеся множества аргументов <tex>\Pi_{i} \subset \Sigma_{i+1}, \Pi_{i} \subset \Pi_{i+1} \Rightarrow \Pi_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}phi</tex>.

{{ТеоремаОпределение|statement definition = Задачей <tex>\Sigma_mathrm{iQBF^{\Pi} = co\Pi__{ik}}</tex> называется объединение удовлетворимых булевых формул с <tex>k</tex> изменениями кванторов, где первым квантором является <tex>\forall</tex>.<br/>|proof = <tex>co\Pi_mathrm{QBF^{\Pi}_{ik}} = \{L\phi \bigm|\exists R(x,y_forall X_{1},\cdots,y_{i}) \in P, p - poly: x \in L \Leftrightarrow \exists y_X_{12} \forall y_X_{23} \cdots Q y_{i} : \forall j |y_j|~\le~p(|x|), Rphi(x,y_X_{1},\cdots,y_X_{ik})\}</tex>,<br/>Из самого выражения для где <tex>co\Pi_X_{i}</tex> очевидно равенство{{---}} попарно непересекающиеся множества аргументов <tex>\phi</tex>.

<tex>PH_\mathrm{1PH} = {\bigcup \atop {k i \in \mathbb{N}}} \Sigma_{i}</tex>.<br/><tex>PH_{2} = {\bigcup \atop {k \in \mathbb{N}}} \Pi_{i}</tex><br/><tex>PH_{3} = {\bigcup \atop {k \in \mathbb{N}}} (\Sigma_{i} \cup \Pi_{i})</tex>

|statement = Все три определения класса <tex>\mathrm{PH</tex> эквивалентны, т.е. <tex>PH_{1} = PH_{2} = PH_\subset \mathrm{3PS}</tex>.|proof = Пусть <tex>L \in \Sigma_{i} \subset \Pi_{i+1} \Rightarrow PH_{1} \subset PH_{2}</tex><br/><tex>exists R : x \Pi_{i} in L \subset (Leftrightarrow \Sigma_exists y_{i+1} \cap \Pi_cdots Q y_{i+1}) \subset : R(\Sigma_x,y_{i+1} ,\cup \Pi_cdots,y_{i+1}) , \Rightarrow PH_forall j |y_{2j} | \subset PH_{3}le poly(|x|)</tex>.<br/>То есть, для перебора всех возможных значений <tex>\Pi_y_{i} \subset \Sigma_{i+1j}</tex> потребуется не более, \Sigma_{чем <tex>i} \subset \Sigma_{i+1} \Rightarrow PH_{3} \subset PH_{1}cdot poly(|x|)</tex>памяти. Заметим, что <tex>i \cdot poly(|x|)<br/tex>тоже полином.Т.о.Таким образом, для любого формального языка из <tex>PH_{1} \subset PH_mathrm{2PH} </tex> существует программа, разрешающая его на полиномиальной памяти. То есть, любой формальный язык из <tex>\subset PH_mathrm{3PH} </tex> принадлежит <tex>\subset PH_mathrm{1PS}</tex>.

{{Теорема|statement = <tex>PH \subset PS</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}| \le poly(|x|)\right.</tex><br/>То есть, для перебора всех возможных значений <tex>y_{j}</tex> потребуется не более, чем <tex>i \cdot poly(|x|)</tex> памяти. Заметим, что <tex>i \cdot poly(|x|)</tex> тоже полином.Таким образом, для любого формального языка из <tex>PH</tex> существует программа, разрешающая его на полиномиальной памяти. То есть, любой формальный язык из <tex>PH</tex> принадлежит <tex>PS</tex>.}}