108
правок
Изменения
Нет описания правки
}
Т.о., <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> очевидно равенство.
}}
