[理工] 演算法 P/NP/NPC

看板Grad-ProbAsk作者 (Clonsey)時間6年前 (2017/11/30 19:55), 6年前編輯推噓6(6推 0噓 8→)
留言14則, 4人參與, 6年前最新討論串1/1
想問一下 同樣在NPC的問題裡, 都視為一樣難嗎? 那這樣所有P裡的問題也都視為一樣難嗎? 例如一個問題O(n)可解, 另一個O(n^2)可解 這樣也視為一樣難嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.163.176.47 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1512042909.A.936.html
推
11/30 21:09, 6年前 , 1F
一樣難是因為可以互相reduction
11/30 21:09, 1F
→
11/30 21:09, 6年前 , 2F
在P裡面談reduce沒有什麼意義
11/30 21:09, 2F
→
11/30 21:10, 6年前 , 3F
因為是規定多項式時間內可以轉換
11/30 21:10, 3F
→
11/30 21:11, 6年前 , 4F
但你解決的時間就是已經多項式時間了
11/30 21:11, 4F
推
11/30 21:27, 6年前 , 5F
以 polynomial-time reduction 的觀點來看 NPC 都是一樣難
11/30 21:27, 5F
→
11/30 21:29, 6年前 , 6F
但是有不同的 reduction 定義 可以區分 NPC 問題的難度
11/30 21:29, 6F
推
11/30 21:44, 6年前 , 7F
感謝樓上演算法大大，長知識惹
11/30 21:44, 7F
推
11/30 22:07, 6年前 , 8F
感謝F大 長知識了
11/30 22:07, 8F
謝謝各位大大! ※ 編輯: clonsey1314 (1.163.176.47), 11/30/2017 22:40:55
推
12/01 11:01, 6年前 , 9F
感謝F大指正！
12/01 11:01, 9F
推
12/01 11:04, 6年前 , 10F
舉例來說，我們可以用 Log-space reduction 來定義 NPC
12/01 11:04, 10F
→
12/01 11:05, 6年前 , 11F
12/01 11:05, 11F
→
12/01 11:05, 6年前 , 12F
有些書是用 log-space reduction 來定義 NPC
12/01 11:05, 12F
→
12/01 11:06, 6年前 , 13F
但是 log-space reduction 和 polynomial-time reduction
12/01 11:06, 13F
→
12/01 11:06, 6年前 , 14F
定義出來的 NPC 是不是等價 仍然是 open question
12/01 11:06, 14F
‣ 更多 clonsey1314 的文章
文章代碼(AID): #1Q7_6Tas (Grad-ProbAsk)