np-為什麼說旅行商問題是NP Hard的？

為什麼說旅行商問題是NP Hard的？

為什麼說旅行商問題是NP Hard的？網上看了很多文章還是比較迷糊，有誰能清晰地講解下。怎麼樣判斷一個算法是不是NP Hard？

最佳回答：

怎樣證明一個問題C是NP完全問題呢？首先，要證明C是NP問題，也就是C的解的正確性容易驗證；然後要證明有一個NP完全問題B，能夠在多項式時間內歸約到C。這就要求必須先存在至少一個NPC問題。Cook證明了NP完全問題的祖先就是SAT。SAT問題是指給定一個包含n個布爾變量的邏輯式，問是否存在一個取值組合，使得該式被滿足。Cook證明了SAT是一個NPC問題，如果SAT容易解決，那麼所有NP都容易解決。