[理工] 演算法NPC問題

[joy7658x348 (LAB準時畢業)]

大家好：

假設我們知道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問題

先謝謝各位了 大家考試加油

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.123.103.134
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1510299459.A.8C2.html
推 alan23273850: 一般來說是從簡單reduce到難的，沒有if and only if
→ alan23273850: 如果可以互推，那必定兩個問題的時間複雜度要一樣
推 FRAXIS: reduction 沒有交換性 但是所有 NPC 問題都可以互相
→ FRAXIS: reduce
推 can18: 原 po 第二段的說法有誤 應該是要存在夠快的方法將A轉換成B
→ can18: 才說A reduce to B
推 can18: 另外原po第一段是可以互相reduce的，原因是因為所有np prob
→ can18: lem都可轉換成NP-hard，又NPC是同時為NP及NP-hard，所以所
→ can18: 有NPC間都可以互相轉換
→ joy7658x348: a大指的時間複雜度是..？因為兩個都是NPC問題 題目只
→ joy7658x348: 有這樣給並無其他條件
→ joy7658x348: c大第二段意思是要加上 可找到polynomial time 的解
→ joy7658x348: 意思嗎？
→ joy7658x348: 謝謝F大的解答
→ joy7658x348: 也謝謝a,c大