108
правок
Изменения
Нет описания правки
== Классы Σ и Π ==
{{Определение
{{Теорема
|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>
<br/>
{{Теорема
|statement = <tex>\Pi_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>
|proof = <tex>\left]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|)\right.</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>\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>\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>.
}}
