Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3SAT-TAUTOLOGY-reducibility — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена Решенные задачи]] на Нерешенные задачи)
Строка 2: Строка 2:
 
[[NP]] = [[CoNP]].
 
[[NP]] = [[CoNP]].
  
[[Категория:Решенные задачи]]
+
[[Категория:Нерешенные задачи
 
[[Категория:P1401]]
 
[[Категория:P1401]]

Версия 07:35, 8 сентября 2017

Покажите, что если 3SAT и TAUTOLOGY полиномиально сводятся к друг другу по Карпу, то NP = CoNP.

[[Категория:Нерешенные задачи