旅行商問題（TSP）為何是 NP-Hard？

核心證明路徑

1. TSP ∈ NP：給定一條路徑，可在多項式時間內驗證其是否訪問所有城市恰好一次且總長度 ≤ K。
2. Hamiltonian Cycle (HC) ≤ₚ TSP：
   • 任取無向圖 G = (V, E)，構造完全圖 G'，邊權：e ∈ E → 1，e ∉ E → 2。
   • 若 G 存在哈密頓環，則 G' 有權重 |V| 的 TSP 解；反之亦然。
   • 構造過程為多項式時間，故 HC 可歸約到 TSP。
3. HC 是 NPC（已知），因此 TSP 是 NP-Hard。結合 (1)，TSP 是 NPC（決策版）。

判斷一個問題是否 NP-Hard

1. 確認該問題的決策版本在 NP 中（可多項式驗證）。
2. 找到一個已知的 NPC 問題（如 SAT、3-SAT、HC、Vertex Cover、Subset Sum）。
3. 構造多項式時間歸約，將已知 NPC 問題的任意實例轉化為目標問題實例，使答案等價。

關鍵里程碑

Cook 定理（1971）證明 SAT 是首個 NPC 問題，開啟了「歸約證明 NPC」的標準化時代。所有後續 NPC 證明均直接或間接歸約自 SAT。