Участник:Ovoynov/TSP-approx — Решение Олега Войнова

Материал из DISCOPAL
Перейти к: навигация, поиск


Если такой алгоритм существует, то он за полиномиальное время решает NP-полную задачу о существовании гамильтонова цикла в графе, что эквивалентно P=NP.

StasFomin (обсуждение) 14:20, 13 декабря 2016 (UTC): Да, не совсем четко было прописано условие. Явно указал, что приближенное решения для коммивояжера ищется на полном графе (иначе в чем смысл?).