PCP и аппроксимируемость/Задачи/TSP-approx — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи на :Решенные задачи)
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 9 промежуточных версий этого же участника)
(нет различий)

Версия 15:49, 20 мая 2020

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