108
правок
Изменения
Нет описания правки
==Классы <tex>\Sigma_{i}</tex> и <tex>\Pi_{i}</tex>==
{{Определение
|definition =
|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> очевидно равенство.
}}
==Класс <tex>PH</tex>==
{{Определение
|definition =
<tex>PH = {\bigcup \atop {k \in \mathbb{N}}} \Sigma_{i} = {\bigcup \atop {k \in \mathbb{N}}} \Pi_{i} = {\bigcup \atop {k \in \mathbb{N}}} (\Sigma_{i} \cup \Pi_{i})</tex>
}}
