Полиномиальная иерархия/Задачи/compliment-in-ph — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 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 \ . | ||
Версия 11:11, 18 апреля 2013