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