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

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

Текущая версия на 00:01, 17 марта 2021