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

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

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

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