Общая задача коммивояжера

Если неравенства треугольника отсутствует, не удается найти хорошее приближение за полиномиальное время.

Теорема.Пусть P¹ NP и r ³ 1. Тогда не существует полиномиального приближенного алгоритма, решающего общую задачу о коммивояжере с ошибкой не более чем в r раз.

Доказательство. Допустим противное, что такой алгоритм A существует для некоторого r ³ 1. Покажем, как использовать алгоритм A для решения задачи о гамильтоновом цикле. Так как задача о гамильтоновом цикле NP-полна, существование решающего ее полиномиального алгоритма влечет P = NP.

Пусть дан граф G=(V, E), и мы хотим узнать, есть ли в нем гамиль- тонов цикл, используя алгоритм A. Дополним граф G до полного графа

G*=(V, E*), на ребрах которого определим функцию стоимости: c(u, v) =

1, если (u, v) Î E, r çV÷ + 1 в противном случае. Время построения G* и c не превосходит полинома от çV÷ и çE÷.

Рассмотрим задачу коммивояжера для графа G* с функцией стоимости c. Если исходный граф G имел гамильтонов цикл, то этот цикл есть решение задачи коммивояжера с суммарной стоимостью çV÷. Если гамильтонова цикла не было, то любое решение задачи о коммивояжере проходит по одному из новых, не содержащихся в E, ребер; cтоимость такого цикла более чем в r раз больше стоимости оптимального цикла из G.

Приближенный алгоритм A, примененный к графу G*, выдаст гамильтонов цикл графа G, если он существует, в противном случае – цикл стоимостью более r çV÷. Тем самым можно отличить один случай от другого за полиномиальное время, откуда следует полиномиальная сложность задачи о гамильтоновом цикле, что неверно. „