Полиномиальная иерархия/Задачи/compliment-in-ph — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показано 20 промежуточных версий 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