多項式時間作為「有效率」

電腦科學家劃下一條著名的界線：若一個演算法的最壞情況執行時間被輸入規模的某個多項式界住，也就是對某固定常數 k 為 O(n^k)，就視為「有效率」。任何需要指數時間的，依此慣例就是「沒效率」或「難解」。這條分界線定義了複雜度類 P（可在多項式時間內解的問題），並支撐起整個 P 對 NP 的問題。

為什麼選多項式作為邊界？三個好理由。第一，穩健性：多項式時間問題的類別，在你切換於合理的計算模型或程式語言之間時不會改變，因為一個模型能以僅僅多項式的額外開銷模擬另一個——所以「多項式」是個與機器無關的概念，不像任何特定的執行時間。第二，封閉性：多項式對加法、乘法與複合封閉，所以用多項式的子步驟搭建多項式演算法，仍保持多項式，這讓這個類別容易推理。第三，經驗觀察（有時稱為柯巴姆-埃德蒙茲論題）：有多項式演算法的問題，實務上往往能得到真正可用的演算法，而指數的則往往卡住。

對這個理想化必須誠實。多項式並不自動表示快：執行時間 n^100 的演算法是多項式卻徹底不切實際，一個帶天文常數的「銀河級」演算法也可以是多項式卻無用。反之，有些指數演算法對實際出現的輸入規模還好。所以「多項式 = 有效率」是個穩健、有理論動機的慣例，是個極佳的第一道過濾，而非每個多項式演算法都在你資料上跑得快的字面承諾。它是關於擴展行為與一條乾淨的類別邊界的陳述，刻意地粗糙。