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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
Строка 5: Строка 5:
 
Докажите, что  <m>SHAM_{3}</m> и <m>DHAM_{3}</m> — NP-трудны.
 
Докажите, что  <m>SHAM_{3}</m> и <m>DHAM_{3}</m> — NP-трудны.
  
[[Категория:Решенные задачи]]
+
[[Категория:Нерешенные задачи]]

Версия 23:52, 3 марта 2021

Пусть

  • — задача поиска гамильтонового цикла в графе , где V — делиться на 3.
  • — задача подтверждения наличия гамильтонового цикла в таком графе.

Докажите, что и — NP-трудны.