旅行推銷員問題（traveling salesman problem）

一位推銷員必須造訪一串城市，每個恰好一次，再回家，沿途支付相鄰城市間的道路距離，並想要最便宜的環行。這就是旅行推銷員問題，也許是所有計算中最著名的最佳化問題。可能路線的數目隨城市數呈階乘爆炸，所以暴力法在幾十個城市以上就無望，但這問題無所不在：物流、晶片佈線、DNA 定序。

它有兩種版本，而這個區別正是這個領域的重點。「最佳化」版——找最小成本路線——是 NP 困難，但（已知）不屬於 NP，因為單一條路線不是「它就是最短」這件事的顯然證書。「判定」版改問：給定預算 B，是否存在總成本至多 B 的路線？這個版本「屬於」NP，因為一條成本至多 B 的路線是驗證器能在多項式時間內加總的證書，且它是 NP 完全。我們把最佳化問題轉成判定問題以納入 NP 框架，再研究判定問題的完全性。

判定版 TSP 是 NP 完全，由一個從漢米頓迴路問題出發的短歸約證得：把每條既有邊的成本設為 1、每條缺失邊的成本設為一個巨大的數，則成本至多 n（城市數）的路線存在，恰恰當漢米頓迴路存在時。TSP 也展示了最壞情況理論與實務之間的落差。一般問題是 NP 困難，但度量版（距離滿足三角不等式）有一個經典的 1.5 倍近似（Christofides），而現代求解器能為數千個城市的實例找到可證明最優的路線。NP 困難是警告，不是高牆。