大家好：
假設我們知道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大