Полиномиальная иерархия/Задачи/compliment-in-ph — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<latex> Для любого натурального $k, \ k \geq 0$, верно соотношение $$ L \in \Sigma^p_k \ \iff \ \{0,1\}^*\setminus L \in \Pi^…») |
StasFomin (обсуждение | вклад) |
||
(не показано 18 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
<latex> | <latex> | ||
− | + | Докажите, что для любого натурального $k, \ k \geq 0$, верно соотношение | |
$$ | $$ | ||
L \in \Sigma^p_k \ \iff \ \{0,1\}^*\setminus L \in \Pi^p_k \ . | L \in \Sigma^p_k \ \iff \ \{0,1\}^*\setminus L \in \Pi^p_k \ . | ||
$$ | $$ | ||
</latex> | </latex> | ||
+ | |||
+ | [[Категория:Нерешенные задачи]] |
Версия 21:01, 16 марта 2021