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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Решенные задачи]] на :Нерешенные задачи]])
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показаны 4 промежуточные версии этого же участника)
Строка 1: Строка 1:
 
Покажите, что если существует полиномиальный f(n)-приближенный алгоритм для задачи о коммивояжере на полном графе с положительными весами, где f любая функция, то P=NP.
 
Покажите, что если существует полиномиальный f(n)-приближенный алгоритм для задачи о коммивояжере на полном графе с положительными весами, где f любая функция, то P=NP.
  
[[Категория:Нерешенные задачи]]
+
[[Категория:Решенные задачи]]

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

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