再利用無向圖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問題