我們達成的那筆交易
到現在，你已經見過複雜度理論的核心交易。我們在沙地上劃下一條線：如果一個演算法的最壞情況執行時間能被輸入大小的某個多項式界住——n、n^2、n^3、甚至 n^100——它就算好的；如果它像 2^n 那樣需要指數時間，就算壞的。線內的一切都歸入 複雜度類別 P，也就是能在確定型機器上以 多項式時間 解出的問題。這是個真正有力的想法，而本篇接下來要誠實地欣賞它：該讚美的地方讚美，該質疑的地方質疑。
為什麼「多項式對指數」這條切線這麼誘人？因為你在第二篇爬過的成長速率階梯。多項式長得很有禮貌。輸入翻倍，n^3 只增大 8 倍——煩，但撐得住。指數則長得很兇狠：輸入只要多一個符號，2^n 就翻倍。在一台每秒做十億步的機器上，n = 60 時的 2^n 就已經超過宇宙的年齡。這道鴻溝不是捨入誤差；它是「程式」和「幻想」之間的差別。
多項式確實是條好線的三個理由
在拆掉這條線之前，先看看為什麼這麼多頭腦清醒的人仍堅守它。第一，穩健性。如第四篇所示，無論你的機器是單帶圖靈機、多帶圖靈機，還是你桌上那種隨機存取電腦，P 都是同一個類別。在合理模型之間轉換只付出多項式級的膨脹，而多項式的多項式仍是多項式。這正是 Cobham–Edmonds 論題的精神：「可行」應該意味著多項式，恰恰因為換了硬體這個標籤也不會晃動。
第二，封閉性。多項式對加法、乘法、複合都封閉。所以如果你用多項式時間的子程序拼出一個大演算法——在一個本身跑多項式次的迴圈裡呼叫某個子程序——整體仍是多項式。正是這點讓我們能用「一層呼叫一層」這種我們實際寫程式的方式來推理，而成本不會在每個接縫處爆炸。
第三，它在自然界劃出了一條真實的界線。那些著名例子並非刻意湊出來的。把 n 個數字排序、在道路網路裡找最短路徑、判定某城是否從另一城可達，甚至檢驗一個數是否為質數——全都舒舒服服住在 P 裡。同時，有一整族像拼圖的問題，也就是 NP 裡的那些，五十年來抵擋了所有人找到的每一個多項式時間演算法。這條線在做誠實的工作：它把我們例行性輾過的問題，和那些不斷讓我們碰壁的問題，切開來。
這套令人安心的說法漏水的地方
現在來談誠實。把「屬於 P」等同於「實務上可行」是個有用的口號，不是定理，而且它在好幾處漏水。第一處漏水是被藏起的常數。big-O 丟掉了前面的乘數。一個 O(n) 但暗地裡做 10^40 * n 步的演算法，紙面上是漂亮的線性時間演算法，在你有生之年卻完全沒用。把 P 等同於可行的侷限正是從這裡開始：多項式說的是成本如何擴張，而不是它有多大。
第二處漏水是指數（次方）。一個帶巨大次方的多項式，在你這輩子會碰到的每個輸入大小上，都可能跟指數一樣絕望。某些著名的理論演算法跑在 n^100 甚至更糟的時間裡；那在技術上是多項式、技術上「屬於 P」、技術上卻跑不動。當 n = 100 時，n^100 已經是 10^200——沒有任何機器，也永遠不會有，能做這麼多步。所以光是「多項式」並不是速度的保證。
另外兩道誠實的皺褶：最壞情況，以及「可行」到底是什麼意思
第三處漏水朝相反方向流。我們整套框架建立在 最壞情況分析之上——我們用一個演算法最慢的可能輸入來評斷它。但最壞情況可能是個從不現身的偏執反派。線性規劃的單純形法在最壞情況下是指數的，然而數十年的實際使用，使它成為運算界最可靠的主力之一，因為那些討厭的輸入稀少到幾乎不存在。所以一個演算法可以「按我們慣用的尺度不屬於 P」，卻仍是你每一天的正確工具。誠實，要往兩個方向都切。
第四道、也最深的皺褶是：「可行」根本不是個數學詞彙。它取決於年份、預算、硬體，以及你多麼需要那個答案。在 1980 年的大型主機上不可行的計算，今天是一支手機 app。複雜度類別 P 是個精確、不隨時間改變的數學物件；「可行」則是會移動的人類判斷。我們借 P 來當可行性的替身，因為它穩定且可證明，但我們絕不該忘記，我們是把一個模糊的概念翻譯成一個鋒利的概念，並暗自希望接縫撐得住。
growth at n = 50, machine does 1e9 steps/sec -------------------------------------------------- n^2 2,500 steps instant n^3 125,000 steps instant n^5 312,500,000 steps ~ 0.3 seconds n^100 ~ 1e170 steps > age of universe (still 'in P'!) 2^n ~ 1.1e15 steps ~ 13 days (NOT in P) n! ~ 3e64 steps > age of universe -------------------------------------------------- lesson: 'polynomial' and 'fast' are correlated, not identical.
為什麼我們仍然保留 P——以及接下來是什麼
面對這麼多漏洞，為何不乾脆扔掉 P？因為替代方案更糟。一個綁在「在我的筆電上一分鐘內跑完」上的定義，會年年改變、機器之間各不相同——它不會是個你能拿來證明定理的穩定物件。P 用一點點真實世界的擬真度，換來巨大的數學槓桿：它穩健、對複合封閉，而且給了我們一個固定的靶子，使得「證明某問題不屬於 P」（或它跟 NP 中最難的問題一樣難）成為一個鋒利而有意義的主張。
這裡是離開這一階的正確方式。把「多項式」讀作可能性的地板，而非實用性的天花板。屬於 P 的問題，是我們有一搏勝算的；只能在指數時間內解的問題——像是硬解一個易驗證卻難拼完的拼圖——則是我們預期會吃力的。「P 即可行」這口號是個好的初步近似，認真的人會把它輕輕地加上引號來引用，從不讓它赤裸裸地出現。
並請注意這留下的懸念。我們有一類能可行求解的乾淨問題，以及一群頑固、像拼圖、抵擋它的問題。自然而然的下一個問題，正是接下來那一階要打開的：那些拼圖即使看似難解，卻很容易驗證——是哪個類別捕捉了這點，它與 P 是什麼關係，而它們之間的落差是真實的、還是我們只是尚未看穿的幻覺？那道門上寫著 NP，而整個電腦科學裡最著名的開放問題，就在門後等著。