Полиномиальная иерархия/Задачи/compliment-in-ph — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<latex> Для любого натурального $k, \ k \geq 0$, верно соотношение $$ L \in \Sigma^p_k \ \iff \ \{0,1\}^*\setminus L \in \Pi^…») |
StasFomin (обсуждение | вклад) |
||
| (не показана 21 промежуточная версия 3 участников) | |||
| Строка 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> | ||
| + | |||
| + | [[Категория:Решенные задачи]] | ||
| + | [[Категория:Теоретические задачи]] | ||
Текущая версия на 06:47, 18 декабря 2023