Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3SAT-TAUTOLOGY-reducibility — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (Массовая правка: замена Решенные задачи]] на Нерешенные задачи) |
||
Строка 2: | Строка 2: | ||
[[NP]] = [[CoNP]]. | [[NP]] = [[CoNP]]. | ||
− | [[Категория: | + | [[Категория:Нерешенные задачи |
[[Категория:P1401]] | [[Категория:P1401]] |
Версия 07:35, 8 сентября 2017
Покажите, что если 3SAT и TAUTOLOGY полиномиально сводятся к друг другу по Карпу, то NP = CoNP.
[[Категория:Нерешенные задачи