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