https://i.imgur.com/NfeMQNo.jpg
想請問有沒有大大能解釋一下如何證明tsp為npc
不太了解為什麼c function要令在原圖沒邊為1 有邊為0?然後還能令k為0
原題應該是給任意非負k都要能回答有沒有tsp吧？

因為是要用tsp的問題解Hamilton cycle, 所以是由Hamilton cycle reduce到 TSP，reduces 後的new graph G’一定存在Hamilton cycle, 令原來Hamilton cycle 的問題為G(V,E) -> G’(V,E’), 其中E是完全圖的邊。 因為Hamiltoncycle 存在G中，所以令裡面的edge weight=0(即原來屬於E的邊), 其他的為1。 因此解完TSP的同時，因為Hamilton cycle 的邊在E中，又因為E的edge weight=0, 所以cost為0， 若不為0則表示沒Hamilton cycle因為可以用poly time Algo 驗證，加上可以由Hamilton cycle reduced to TSP,所以TSP是NP complete

感謝回答 我又回去看了一下定義 本來以為reduce是要兩邊都可以互相用演算法解 但應該實際上應該是單向關係

是可以互相reduce 因為那是NP hard的性質～也謝謝你上次細心回答我的問題

應該說reduce本身是單向的 但是證明reduce是證明對於「任何」A問題的instance可以轉換成一個B問題 兩個問題的轉換是雙向 我本來以為也要對於任何B問題的instance也成立才行qq

NP-Hard 不保證可以互相 polynomial-time reduce..NPC的問題是可以互相 polynomial time reduce證明是在說明G有HC若且唯若G'有0成本 TSP所以比較完整的證明法會分兩步G 中有 HC 則 G' 中必有 0 成本 TSP再證 G' 有 0 成本 TSP 則 G 中必有 HC（或是證明 G 中沒有 HC 則 G' 中必無 0 成本 TSP)雖然這邊看起來是在證明雙向 但是實際只是在證明單向..

感謝點明觀念，我的意思可能沒表達清楚可以互相reduce但不一定都是polynomial time, NPC則是一定可以在polynomial time 互相reduces