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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи на :Решенные задачи)
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 12 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
Покажите, что если язык ГАМИЛЬТОНОВ ГРАФ ∈ P , то за полиномиальное время можно не только определить, что граф гамильтонов, но и найти в нем какой-нибудь гамильтонов цикл (если он существует).
 
Покажите, что если язык ГАМИЛЬТОНОВ ГРАФ ∈ P , то за полиномиальное время можно не только определить, что граф гамильтонов, но и найти в нем какой-нибудь гамильтонов цикл (если он существует).
  
 
+
[[Категория:Решенные задачи]]
[[Category:Решенные задачи]]
+
[[Категория:Теоретические задачи]]

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

Покажите, что если язык ГАМИЛЬТОНОВ ГРАФ ∈ P , то за полиномиальное время можно не только определить, что граф гамильтонов, но и найти в нем какой-нибудь гамильтонов цикл (если он существует).