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

Ссылки сюда (5) →

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

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

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

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