108
правок
Изменения
Нет описания правки
{{Определение
|definition =
<tex>\Sigma_{i} = \{L|\exists R(x,y_{1},\cdots,y_{i}) \in 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>.
}}
{{Определение
|definition =
<tex>\Pi_{i} = \{L|\exists R(x, y_{1},\cdots,y_{i}) \in 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} = co\Pi_{i}</tex>.
|proof = <tex>co\Pi_{i} = \{L|\exists R(x,y_{1},\cdots,y_{i}) \in P, p </tex> {{- --}} <tex>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> очевидно равенство.
}}
Таким образом, для любого формального языка из <tex>PH</tex> существует программа, разрешающая его на полиномиальной памяти. То есть, любой формальный язык из <tex>PH</tex> принадлежит <tex>PS</tex>.
}}
/tex>.
|proof =
