假設哈密頓問題是NPC,證明:TSP（旅行商問題）屬於NP-hard問題（現代優化計算方法 邢文旬主編 P50第11題）

再利用無向圖G構造tsp的圖G'，圖G中存在的邊權值設為1，圖G中不存在的邊權值設為X（X>1的整數）。

這樣得到的壹個TSP問題可使用算法A（·）來解。

圖靈規約條件：（1）問題1，問題2都是搜索問題；

（2）求解問題1的算法A（·）可求解問題2；

（3）算法A（問題1）時間復雜度是多項式時間，則算法A(問題2)也是多項式時間；

所以HC可以圖靈規約到這樣壹個TSP問題實例。

又因為HC是NPC類問題，可以圖靈規約到TSP，所以TSP是NP-hard問題