大家好：
假设我们知道Hamilton cycle 可以reducible到TSP问题，那么我们可以说TSP问题也可以
reducible到Hamilton cycle问题吗？若可以的话为什么呢？
因为reducible不是只要B的时间高于或等于A的复杂度，就可说：
A reducible to B
并且我也知道reducible有递遗性，即A reducible B , B reducible to C ,那A 就可 re
ducible to C
不过不确定有没有交换性
毕竟Hamilton cycle 跟TSP都是NPC问题
先谢谢各位了 大家考试加油

一般来说是从简单reduce到难的，没有if and only if如果可以互推，那必定两个问题的时间复杂度要一样

reduction 没有交换性 但是所有 NPC 问题都可以互相reduce

原 po 第二段的说法有误 应该是要存在够快的方法将A转换成B才说A reduce to B另外原po第一段是可以互相reduce的，原因是因为所有np problem都可转换成NP-hard，又NPC是同时为NP及NP-hard，所以所有NPC间都可以互相转换

a大指的时间复杂度是..？因为两个都是NPC问题 题目只有这样给并无其他条件c大第二段意思是要加上 可找到polynomial time 的解意思吗？谢谢F大的解答也谢谢a,c大