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

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 19 промежуточных версий 3 участников)
Строка 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 \ .
Строка 6: Строка 6:
 
</latex>
 
</latex>
  
[[Category:Нерешенные задачи]]
+
[[Категория:Решенные задачи]]
 +
[[Категория:Теоретические задачи]]

Текущая версия на 06:47, 18 декабря 2023