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