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

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

Версия 09:53, 26 февраля 2015

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