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

[clonsey1314 (Clonsey)]

想問一下
同樣在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
推 nat99up: 一樣難是因為可以互相reduction
→ nat99up: 在P裡面談reduce沒有什麼意義
→ nat99up: 因為是規定多項式時間內可以轉換
→ nat99up: 但你解決的時間就是已經多項式時間了
推 FRAXIS: 以 polynomial-time reduction 的觀點來看 NPC 都是一樣難
→ FRAXIS: 但是有不同的 reduction 定義 可以區分 NPC 問題的難度
推 alan23273850: 感謝樓上演算法大大，長知識惹
推 can18: 感謝F大 長知識了
謝謝各位大大!
※ 編輯: clonsey1314 (1.163.176.47), 11/30/2017 22:40:55
推 nat99up: 感謝F大指正！
推 FRAXIS: 舉例來說，我們可以用 Log-space reduction 來定義 NPC
→ FRAXIS: https://en.wikipedia.org/wiki/Log-space_reduction
→ FRAXIS: 有些書是用 log-space reduction 來定義 NPC
→ FRAXIS: 但是 log-space reduction 和 polynomial-time reduction
→ FRAXIS: 定義出來的 NPC 是不是等價 仍然是 open question