algorithm - ハミルトニアン経路が NP 完全であるのに、なぜ TSP は NP 困難なのですか?

Question

これらの 2 つの問題、つまりTSPとハミルトニアン パスの問題がどちらも NP 完全ではないのはなぜですか?

それらは同一に見えます。

Answer 1

NP 硬度と NP 完全性の定義は関連していますが、異なります。具体的には、NP のすべての問題が多項式時間でそれに還元される場合、その問題は NP 困難であり、NP 困難であり、NP 内のそれ自体の両方である場合、その問題は NP 完全です。

クラス NP は、決定問題 (はい/いいえの答えがある問題) で構成されます。その結果、期待される答えはイエスかノーではなく数字であるため、TSP は NP に入ることができません。したがって、TSP は NP 困難になる可能性がありますが、NP 完全になることはできません。

一方、ハミルトニアン経路問題はイエス/ノーの答えを求め、たまたま NP になっています。したがって、NP 困難でもあるため、NP 完全です。

ここで、TSP を「最も安価なパスは何か」という質問から変更することで、意思決定問題に変換できます。「コストがX以下のパスはありますか?」と、後者の定式化はNPであり、たまたまNP完全です。