Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Гамильтонов граф — различия между версиями
Материал из DISCOPAL
Vitaliy (обсуждение | вклад) (Новая страница: «Category:Предложенные студентами задачи <latex> Покажите, что если язык ГАМИЛЬТОНОВ ГРАФ ∈ P …») |
StasFomin (обсуждение | вклад) м (StasFomin переименовал страницу Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Гамильтонов граф в [[Полиномиальные сводимости…) |
||
(не показано 14 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
− | |||
− | |||
Покажите, что если язык ГАМИЛЬТОНОВ ГРАФ ∈ P , то за полиномиальное время можно не только определить, что граф гамильтонов, но и найти в нем какой-нибудь гамильтонов цикл (если он существует). | Покажите, что если язык ГАМИЛЬТОНОВ ГРАФ ∈ P , то за полиномиальное время можно не только определить, что граф гамильтонов, но и найти в нем какой-нибудь гамильтонов цикл (если он существует). | ||
+ | |||
+ | [[Категория:Решенные задачи]] |
Версия 17:16, 11 октября 2020
Покажите, что если язык ГАМИЛЬТОНОВ ГРАФ ∈ P , то за полиномиальное время можно не только определить, что граф гамильтонов, но и найти в нем какой-нибудь гамильтонов цикл (если он существует).