NP 不是指「非多項式」（NP does not mean non-polynomial）

這是整個複雜度理論中最常見的單一誤解。人們看到「NP」就讀成「non-polynomial（非多項式）」，彷彿它指的是那些慢而難解的問題。並非如此。N 代表「非確定型（nondeterministic）」、P 代表「多項式時間（polynomial time）」：NP 是「非確定型多項式時間」。把它讀成「非多項式」既弄錯字母也弄錯意義，並會引發一連串錯誤結論。

為何這個混淆要緊？因為「非多項式」會暗示 NP 問題依定義就無法在多項式時間內求解，那就表示 P 與 NP 顯然不同、根本不會有什麼著名的未解問題。真相恰恰相反：每個能在確定型多項式時間內求解的問題「也」屬於 NP（只要忽略證書即可），所以 P 是 NP 的子集。排序、最短路徑、質數判定，全都安穩地坐在 NP 之內。NP 不是難題俱樂部；它是「可高效驗證問題」的俱樂部，連容易的也是會員。

正確的心智模型是：NP＝那些「是」答案具有短而能在多項式時間內檢查的證書的問題，等價地，是一台非確定型機器能在多項式時間內求解的問題。NP 是否含有真正比 P 更難（無法在多項式時間內求解）的問題，正是懸而未決的 P 對 NP 問題。所以當你聽到「這問題是 NP 完全」，它本身「並不」表示「已被證明需要指數時間」。它表示「在 NP 中最難的一群」，而這份難度，是以那條廣為相信但尚未證明的猜想——P 不等於 NP——為條件的。