[理工] 演算法NPC問題

看板Grad-ProbAsk作者 (LAB準時畢業)時間8年前 (2017/11/10 15:37), 編輯推噓4(4推 0噓 11→)
留言15則, 4人參與, 8年前最新討論串1/1
大家好： 假設我們知道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
推
11/10 16:46, 8年前 , 1F
一般來說是從簡單reduce到難的，沒有if and only if
11/10 16:46, 1F
→
11/10 16:52, 8年前 , 2F
如果可以互推，那必定兩個問題的時間複雜度要一樣
11/10 16:52, 2F
推
11/11 05:30, 8年前 , 3F
reduction 沒有交換性 但是所有 NPC 問題都可以互相
11/11 05:30, 3F
→
11/11 05:30, 8年前 , 4F
reduce
11/11 05:30, 4F
推
11/11 07:54, 8年前 , 5F
原 po 第二段的說法有誤 應該是要存在夠快的方法將A轉換成B
11/11 07:54, 5F
→
11/11 07:54, 8年前 , 6F
才說A reduce to B
11/11 07:54, 6F
推
11/11 08:18, 8年前 , 7F
另外原po第一段是可以互相reduce的，原因是因為所有np prob
11/11 08:18, 7F
→
11/11 08:18, 8年前 , 8F
lem都可轉換成NP-hard，又NPC是同時為NP及NP-hard，所以所
11/11 08:18, 8F
→
11/11 08:18, 8年前 , 9F
有NPC間都可以互相轉換
11/11 08:18, 9F
→
11/12 03:19, 8年前 , 10F
a大指的時間複雜度是..？因為兩個都是NPC問題 題目只
11/12 03:19, 10F
→
11/12 03:19, 8年前 , 11F
有這樣給並無其他條件
11/12 03:19, 11F
→
11/12 03:20, 8年前 , 12F
c大第二段意思是要加上 可找到polynomial time 的解
11/12 03:20, 12F
→
11/12 03:20, 8年前 , 13F
意思嗎？
11/12 03:20, 13F
→
11/12 03:21, 8年前 , 14F
謝謝F大的解答
11/12 03:21, 14F
→
11/12 03:22, 8年前 , 15F
也謝謝a,c大
11/12 03:22, 15F
‣ 更多 joy7658x348 的文章
文章代碼(AID): #1Q1LT3Z2 (Grad-ProbAsk)