引言
漢密爾頓路徑問題是一個典型的NP完全問題，看下面的視訊能有一個直覺印象。
【Ted-ED】病毒謎題：漢密爾頓路徑/NP完全問題 The Virus Riddle
定義
P（Polynomial）：在多項式時間内可解的判定問題
NP（Non-deterministic Polynomial）：在多項式時間内可驗證的判定問題
NP-hard（NP難）：難度不低于所有NP問題的問題
NPC(NP完全)：NP-hard問題與NP問題的交集，即所有NP問題中最難的
可以把多項式時間驗證算法看成下面不确定的方式搜尋證據空間：對給定的執行個體I，“猜想”一個t，檢查t能否證明I就是所求的解。猜想和檢查都可在多項式時間内完成，并當且僅當I是解時能正确地猜想到一個證據t。這種不确定的搜尋方式，稱作非确定型多項式時間算法（普通算法稱為确定性算法）。一個判定問題∈NP，當且僅當該問題存在非确定型多項式時間算法。非确定型多項式時間算法隻是為了刻畫可驗證性提出的概念，為了得到确定的結果，必須搜尋整個可能的證據空間，通常需要指數級時間。
NPC問題舉例：判定一個圖中是否存在Hamilton回路。猜想一個路徑，很容易在多項式時間驗證它是否符合要求。一旦猜中一個路徑，該路徑必是最優解。
非NP問題舉例：判定一個圖中是否不存在Hamilton回路。這樣問題就沒法在多項式的時間裡進行驗證了，除非試過所有路徑，否則你不敢斷定它“沒有Hamilton回路”。
P、NP、NP-hard、NPC關系如下：
證明屬于NP
最簡單的方法是使用NP問題的“證據定義”（certificate definiiton）。直覺上，一個問題是NP問題當且僅當存在 多項式時間的驗證算法 + 多項式規模的證據。
例如，想檢查m是否是合數，可通過以下步驟：
- 證據格式：一組數字(a, b)
- 驗證算法：當且僅當1 < a, b < m且 ab = m時，接受證據(a, b)
若m是合數，則存在一對數字(a, b)滿足條件且大小為O(logm)。（輸入大小是m，輸入規模是logm）
若m不是合數，則不存在這樣的一對數字。
約化/歸約（Reducibility）
約化：如果有一個多項式的時間的變化法則，對任意一個程式A的輸入，都能按這個法則變換成程式B的輸入，使兩程式的輸出相同，那麼我們說，問題A可約化為問題B。
即可以用問題B的解法解決問題A，A問題隻是B問題的特殊情況。比如求解一進制一次方程可以約化為求解一進制二次方程（二次項為0）。顯然，B的難度必定大于等于A。
例如：
TSP問題（Traveling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市隻能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目标是要求得的路徑路程為所有路徑之中的最小值。
Hamilton回路可以約化為TSP問題。在Hamilton回路問題中，兩點相連即這兩點距離為1，兩點不直接相連則令其距離為2，于是問題轉化為在TSP問題中是否存在一條長為|V|的路徑（TSP中路徑長度>=|V|）。Hamilton回路存在當且僅當TSP問題中存在長為|V|的回路。
所有的NP問題都可以約化為同一類問題——NPC問題！即NPC問題是所有NP問題的泛化問題。
證明屬于NPC
證明問題B屬于NPC，關鍵是找一個已知的NPC問題A，将問題A約化到問題B即可。
有一個最“簡單”的NPC問題，可以由它出發約化出一系列NPC問題，它就是SAT問題（可滿足性）。
圖中越往下的問題越泛化，越難解。
是以證明屬于NPC的步驟為：
- 證明問題B屬于NP（起碼是多項式時間可驗證的）
- 證明某NPC問題A，能夠在多項式時間内歸約到問題B（比某個NPC還難）
一個簡單例子，證明最大可滿足性MAX-SAT屬于NPC。
MAX-SAT：任給關于變元x1, x2, …, xn的簡單析取式C1, C2, …, Cm及正整數K，問存在關于變元x1, x2, …, xn的指派使得C1, C2, …, Cm中至少有K個為真嗎？
證明：
- 任意猜想一個關于變元x1, x2, …, xn的指派，不難檢查C1, C2, …, Cm中是否至少有K個為真，是以MAX-SAT∈NP；
- SAT可以看做MAX-SAT的子問題，容易把SAT多項式時間變換到它。對SAT的每一個執行個體I，I是關于變元 x1, x2, …, xn的合取範式 F = C1 ∧ C2 ∧ … ∧ Cm，其中Ci是簡單析取式；對應的MAX-SAT的執行個體f(I)由簡單析取式 C1 ，C2， … ，Cm 和正整數K = m構成。顯然f是多項式時間可計算的，且指派t是F的成真指派當且僅當t使C1 ，C2， … ，Cm 都成真，進而I的答案是“Yes”當且僅當f(I)的答案是“Yes”。
得證SAT≤pMAX-SAT。
參考資料
P、NP、NPC和NP-Hard相關概念的圖形和解釋
How to show that problems are in NP?