Почему TSP NP-жесткий, а гамильтоновский путь NP-полный?

Question

Почему не эти 2 проблемы, а именно TSP и Hamiltonian path problem, оба NP-полные?

Они кажутся одинаковыми.

Answer 1

Для задачи X быть NP-полной, он должен удовлетворять:

1. X в НП, учитывая решение X, то решение может быть проверено в полиномиальное время.
2. X находится в NP-hard, то есть каждая проблема NP сведена к ней в полиномиальное время (вы можете сделать это за счет сокращения от известной NP-жесткой проблемы (например, гамильтонова траектория)).

Есть две версии коммивояжер задачи (TSP):

1. от версии оптимизации (вероятно, один вы смотрите), а именно, найти оптимальное решение TSP , Это не проблема решения и, следовательно, не может быть в NP, но, тем не менее, NP-hard может быть доказана через Hamiltonian Path reduction. Поэтому это не полная проблема NP.
2. Версия решения - если задано целое число K, существует ли путь по каждой вершине на графике длины < K? Это решение (да/нет), и решение может быть проверено в полиномиальное время (просто пересечь путь и посмотреть, касается ли оно каждой вершины), и поэтому оно находится в NP, но оно также находится в NP-hard (by аналогичное доказательство, как указано выше). Поскольку он удовлетворяет обоим требованиям для полноты NP, это NP-полная проблема.

Answer 2

Определения NP-твердости и NP-полноты связаны друг с другом, но различны. В частности, проблема NP-жесткая, если каждая проблема в NP сводится к ней в полиномиальное время, и проблема NP-полная, если она NP-hard и сама в NP.

Класс NP состоит из проблем с решением проблем, у которых есть ответ «да/нет». В результате TSP не может быть в NP, потому что ожидаемый ответ - это число, а не да или нет. Поэтому TSP может быть NP-жестким, но он не может быть NP-полным.

С другой стороны, проблема пути гамильтониана задает ответ «да/нет», и это происходит в NP. Поэтому, так как он NP-жесткий, он NP-полный.

Теперь вы можете принять TSP и преобразовать его в решение проблемы, изменив вопрос с вопроса «что такое самый дешевый путь?». «есть ли путь, который стоит X или меньше?», и эта последняя формулировка находится в NP, а также оказывается NP-полной.