108
правок
Изменения
Нет описания правки
|definition =
<tex>\Sigma_{i} = \{L|\exists R(x,y_{1},\cdots,y_{i}) \in P, p - 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>.
}}
|definition =
<tex>\Pi_{i} = \{L|\exists R(x, y_{1},\cdots,y_{i}) \in P, p - 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>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|)</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>.
<br/>
<tex>R'(x,y_{1},\cdots,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>.
<br/>
<tex>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_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>.|proof = Пусть <tex>L \in \Pi_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \forall y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i}), \forall j |y_{j}| \le poly(|x|)</tex>.<br/>Проверим, что <tex>L \in \Pi_{i+1} \Leftrightarrow \exists R' : x \in L \Leftrightarrow \forall y_{1} \cdots Q y_{i} \bar{Q} y_{i+1} : R'(x,y_{1},\cdots,y_{i},y_{i+1})</tex>.
<br/>
<tex>R'(x,y_{1},\cdots,y_{i+1})</tex> {
return <tex>R(x,y_{1},\cdots,y_{i})</tex>;
}
Проверим, что <tex>L \in \Sigma_{i+1} \Leftrightarrow \exists R'' : x \in L \Leftrightarrow \exists y_{0} \forall y_{1} \cdots Q y_{i} : R''(x,y_{0},y_{1},\cdots,y_{i})</tex>.
<br/>
<tex>R''(x,y_{0},y_{1},\cdots,y_{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}</tex>.
{{Теорема
|statement = <tex>\Sigma_{i} = co\Pi_{i}</tex>.|proof = <tex>co\Pi_{i} = \{L|\exists R(x,y_{1},\cdots,y_{i}) \in P, p - poly: x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \cdots Q y_{i} : \forall j |y_j|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\}</tex>.<br/>
Из самого выражения для <tex>co\Pi_{i}</tex> очевидно равенство.
}}
{{Определение
|definition =
<tex>PH_{1} = {\bigcup \atop {k \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>PH</tex> эквивалентны, т.е. <tex>PH_{1} = PH_{2} = PH_{3}</tex>.|proof = <tex>\Sigma_{i} \subset \Pi_{i+1} \Rightarrow PH_{1} \subset PH_{2}</tex>.<br/><tex>\Pi_{i} \subset (\Sigma_{i+1} \cap \Pi_{i+1}) \subset (\Sigma_{i+1} \cup \Pi_{i+1}) \Rightarrow PH_{2} \subset PH_{3}</tex>.<br/><tex>\Pi_{i} \subset \Sigma_{i+1}, \Sigma_{i} \subset \Sigma_{i+1} \Rightarrow PH_{3} \subset PH_{1}</tex>.<br/>Т.о., <tex>PH_{1} \subset PH_{2} \subset PH_{3} \subset PH_{1}</tex>.
}}
{{Теорема
|statement = <tex>PH \subset PS</tex>.|proof = Пусть <tex>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|)</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>.
}}
