Полиномиальная иерархия/Задачи/compliment-in-ph — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
<latex>
 
<latex>
Для любого натурального $k, \ k \geq 0$, верно соотношение
+
Докажите, что для любого натурального $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