задача коммивояжера нп полная. подскажите доказательство

Finn

Подскажите плз где найти толковое доказательство,
что задача коммивояжера нп полная, если известно, что гамильтонов цикл нп полный.
задача коммивояжера в данном случае выглядит как "найти цикл веса меньше Х"

Zoltan

попробуй тут - http://www.math.nsc.ru/LBRT/k5/lec8.pdf

Xephon

В задаче коммивояжёра надо появиться в каждом городе хотя бы один раз.
Пусть N вершин в графе. Тогда делаем вес ребра равным 1. Задача — найти цикл длины <=N.
Это равносильно тому, что мы появимся в каждом городе ровно 1 раз, т.е. цикл гамильтонов.

olga1507

Типичная ошибка, но на нее как правило не обращают внимания.
Когда мы говорим про сложность, то задача должна иметь ответ Да\Нет, а не найти там что-либо. С формальной точки зрения между этими вещами есть разница. Следовательно NP полной задачей является задача не "найти путь веса меньше X", а "существует ли пусть веса меньше X"

Xephon

Можно сказать, что нужно найти k-ый бит неким образом заранее формализованного ответа.
Чтобы запустив программу для всех k мы получили верный ответ.
А вот задача очень часто подразумевает ответ "да, существует", но хрен найдёшь.
Оставить комментарий
Имя или ник:
Комментарий: