SOの回答の1つで次を読みました。
巡回セールスマン問題は、通常、すべての都市を結ぶ最も安いルートを見つけることです。これは意思決定の問題ではなく、提案された解決策を直接検証することはできません。これを決定問題として言い換えることができます: コスト C が与えられた場合、C よりも安いルートはありますか? この問題は NP 完全であり、少しの作業で元の TSP を、変更された NP 完全な形式とほぼ同じくらい簡単に解くことができます。したがって、TSP は少なくとも NP 完全問題と同じくらい難しいため、NP 困難です。
TSP が NP-Complete であることは理解していますが、どのように問題が NP-Hard なのですか? NP にあるが P にない問題は NP-Hard であると読みました。このことを TSP に関連付けることはできません。これを説明してください。