Просмотр исходного текста страницы Полиномиальная иерархия/Задачи/compliment-in-ph

<latex>
Докажите, что для любого натурального $k, \ k \geq 0$, верно соотношение
$$
L \in \Sigma^p_k \ \iff \ \{0,1\}^*\setminus L \in \Pi^p_k \ .
$$ 
</latex>

[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]