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

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

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