Изменения

<tex>\Sigma_{i}</tex> {{---}} <tex>= \{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>.

<tex>\Pi_{i}</tex> {{---}} <tex>= \{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>.}} ==Взаимоотношения между классами <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})\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/> <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>.