漢米頓迴路的 NP 完全性（NP-completeness of Hamiltonian cycle）
/ Hamiltonian = ham-il-TOH-nee-un /
漢米頓迴路是一趟穿越網路的環行，造訪「每一座」城市恰好一次再回到起點。它聽起來像比較友善的歐拉問題（每座橋恰走一次），而那是容易的——但造訪每個「頂點」一次（而非每條邊一次）卻變得殘酷地難。漢米頓迴路問題問：給定的圖究竟有沒有這樣一趟環行？這是旅行推銷員問題的組合核心，而證明它為 NP 完全是這座動物園裡的一座里程碑。
屬於 NP 是立即可見的：憑證就是提議的頂點順序 v1, v2, ..., vn, v1，而驗證器在 O(n) 時間內檢查相鄰頂點之間有邊、且全部 n 個頂點各出現恰好一次。困難的那一半是 NP 困難性，靠把一個已知的 NP 完全問題——經典上是 3-SAT 或頂點覆蓋——用「裝置」歸約到漢米頓迴路來證明。構想是：建一張圖，使它的漢米頓迴路恰好對應到來源問題的解。每個變數變成一個小小的「雙向街道」裝置，迴路可由左到右或由右到左穿過它，編碼真或假；每個子句變成一個裝置，迴路只有在它至少一個文字被設成滿足它時才能穿線而過。這些零件被接線成：一條穿過整張圖的漢米頓迴路存在，當且僅當存在一組滿足每個子句的一致真值指派。因為每個裝置都是固定大小的局部小機關、且只有多項式多個，這個構造在多項式時間內執行，給出 3-SAT <=p 漢米頓迴路；再加上屬於 NP，漢米頓迴路便是 NP 完全。
它為何超出自身陳述而重要：它是通往旅行推銷員問題的門戶。給定一個漢米頓迴路實例，在現有的邊上放權重 1，在缺失的邊上放一個巨大權重；那麼總權重為 n 的旅程存在，當且僅當漢米頓迴路存在——所以 漢米頓迴路 <=p TSP 決定問題，使 TSP 也成為 NP 困難。兩個誠實的提醒。第一，留意那些表親：歐拉迴路（每條邊一次）可在多項式時間內判定，而長得很像的漢米頓迴路（每個頂點一次）卻是 NP 完全——一個著名的提醒：表面相似對複雜度毫無發言權。第二，NP 困難性是最壞情況：真實的道路網路與許多有結構的圖在實務上容許快速的精確或近最優解，所以「NP 完全」標記的是最壞的實例，而非永遠禁止解這個問題。
從漢米頓迴路到 TSP：取任意 n 個頂點的圖 G，定義距離矩陣，若 uv 是 G 的一條邊則 d(u,v) = 1，否則 d(u,v) = 2。現在問 TSP 問題「存在長度 <= n 的旅程嗎？」。這樣的旅程只用權重 1 的步，亦即只用真實的邊，造訪每座城市一次——恰好是 G 的一條漢米頓迴路。所以解出這個 TSP 實例就回答了漢米頓迴路問題。
漢米頓迴路 <=p TSP：邊上權重 1、非邊上大權重；長度為 n 的旅程＝一條漢米頓迴路。
別和歐拉迴路搞混。造訪每條「邊」一次（歐拉）屬於 P，檢查頂點度數即可判定；造訪每個「頂點」一次（漢米頓）卻是 NP 完全。措辭幾乎相同，複雜度卻相反——一個生動的警告：別憑外表判斷難度。