Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/p-looks-unclosed-under-coding — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «K(L) — кодировка. Докажите, что класс P замкнут относительно кодировок тогда и только то…»)
 
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 2: Строка 2:
  
 
Докажите, что класс P замкнут относительно кодировок тогда и только тогда, если P=NP.
 
Докажите, что класс P замкнут относительно кодировок тогда и только тогда, если P=NP.
 +
 +
[[Категория:Решенные задачи]]
 +
[[Категория:Теоретические задачи]]

Текущая версия на 06:50, 4 мая 2023

K(L) — кодировка.

Докажите, что класс P замкнут относительно кодировок тогда и только тогда, если P=NP.