想問一下
同樣在NPC的問題裡, 都視為一樣難嗎?
那這樣所有P裡的問題也都視為一樣難嗎?
例如一個問題O(n)可解, 另一個O(n^2)可解
這樣也視為一樣難嗎?

一樣難是因為可以互相reduction在P裡面談reduce沒有什麼意義因為是規定多項式時間內可以轉換但你解決的時間就是已經多項式時間了

以 polynomial-time reduction 的觀點來看 NPC 都是一樣難但是有不同的 reduction 定義 可以區分 NPC 問題的難度

感謝樓上演算法大大，長知識惹

感謝F大 長知識了

感謝F大指正！

舉例來說，我們可以用 Log-space reduction 來定義 NPChttps://en.wikipedia.org/wiki/Log-space_reduction有些書是用 log-space reduction 來定義 NPC但是 log-space reduction 和 polynomial-time reduction定義出來的 NPC 是不是等價 仍然是 open question