PCP и аппроксимируемость/Задачи/TSP-approx

Материал из DISCOPAL
< PCP и аппроксимируемость‎ | Задачи
Версия от 17:37, 20 декабря 2012; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Покажите, что если существует полиномиальный f(n)-приближенный алгоритм для задачи о коммивояжере, где f любая функция, то P=NP.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.

Источник — «https://discopal.ispras.ru/index.php?title=PCP_и_аппроксимируемость/Задачи/TSP-approx&oldid=807»