從數步數到替一個類別命名
你已從這一階帶著兩件工具。第一，你會把一台機器的執行時間量成它對每個規模 n 的最壞輸入所花的步數，而不是平均、也不是運氣好的情況。第二，你能透過大 O這副眼鏡讀懂成長率——它丟掉常數與低次項，只留下成本隨 n 增大時膨脹得有多快。本篇把這兩件工具用在一個目的上：畫下單一、銳利的一條線，把我們稱為「可有效求解」的問題，與不算可有效求解的問題分開。
這就是那條線。一個判定問題（答案是是／否的那種）屬於 P 類，如果存在某台確定性圖靈機——就是你在前面一階遇過的那台「無盡筆記本」機器，一個讀寫頭一格一格地讀、擦、重寫——判定它（永遠停機並給出正確的是／否），且時間被輸入規模的某個多項式所界定。「多項式」意思是步數對某個固定指數 k 是 O(n^k)：O(n)、O(n log n)、O(n^2)、O(n^3) 等等全都允許，但 2^n 不行。這就是 P 的全部定義。本篇其餘一切，都是在拆解為什麼這條線值得畫。
為什麼多項式勝過指數，用數字說話
為什麼挑多項式當分界線，而不是比方說「任何低於十億步的東西」？因為多項式對指數的落差不是程度問題——它是一堵牆。像 n^3 這樣的多項式，當你把 n 加倍時只乘上一個常數倍率（n 加倍會讓 n^3 乘上 8）。像 2^n 這樣的指數則以平方級的跳躍成長——n 加上十，成本就乘上約一千。再聰明的常數、再快的晶片都遮不住這一點。把你電腦的速度加倍，只讓 2^n 演算法多吃下一個單位的輸入。這個直白的事實，正是難解性的核心。
input size n n^2 n^3 2^n
10 100 1,000 ~1,000
20 400 8,000 ~1,000,000
50 2,500 125,000 ~10^15
100 10,000 1,000,000 ~10^30
At a billion (10^9) steps per second:
2^100 steps ~ 10^30 / 10^9 = 10^21 seconds
~ 30,000,000,000,000 years
n^3 at n=100 = 1,000,000 steps = 0.001 second看看這張表，這個選擇便自我辯護了。到 n = 100，n^3 演算法約一毫秒就結束，而 2^n 演算法所需的秒數比宇宙至今經歷的還多。這就是指數爆炸在實務上的意思：不是「慢」，而是「一旦 n 連中等都算不上，就永遠無法在任何人類或宇宙的時間尺度內結束」。多項式，無論指數多大，最終都會落到任何固定指數之下。所以「在 P 中」是個承諾：成本成長的方式，是加速與耐心追得上的；「只知道指數演算法」則是個警告：它們追不上。
誰住在 P 裡：那些熟悉的主力
P 不是個抽象的俱樂部——它擠滿了你會稱為「家常便飯」的問題。圖可達性：給定一張由節點構成的網路，加上一個起點與終點，兩者之間有沒有路徑？一次廣度優先搜尋先標記起點，再標記一步可達的全部、接著兩步可達的，如此推進；它對每個節點與每條邊至多碰固定多次，所以執行時間與圖的大小成線性——穩穩是多項式。對 n 個項目排序用合併排序是 O(n log n)，舒舒服服落在多項式內。邊權非負的最短路徑可由 Dijkstra 演算法在大約 O(n^2) 或更好內解決。這些每一個都是 P 的正式成員。
最受讚譽的成員是 PRIMES（質數判定）：給定整數 N，它是質數嗎？數十年來人們有快速方法，但要嘛是隨機化的、要嘛未獲證明，而「是否存在一個有保證的、確定性的多項式時間檢驗」一直是個未決問題。2002 年 AKS 演算法定下此事：PRIMES 在 P 中。這裡藏著一個關鍵的微妙處，正是第 1 篇的輸入規模教訓。N 的輸入規模是寫出 N 所需的位數，約 log N，而非 N 的值本身。一個「就把每個小於 N 的因數都試一遍」的演算法，執行時間與 N 成正比，也就是 2^(位數)——對輸入規模而言是指數，不是多項式。把「值」與「位數」搞混，是把數論演算法貼錯標籤的頭號常見方式。
為什麼 P 很穩健：它幾乎不在乎你用哪種機器
一個合理的疑慮：「多項式時間」難道不取決於圖靈機那些挑剔的細節嗎？如果我讓它多一條帶子、或有隨機存取記憶體、或改用真實語言寫程式，步數不會變嗎？它確實會變——但只變一個多項式倍率，而多項式的多項式仍是多項式。這就是讓 P 值得定義的那個安靜的奇蹟。把一台 k 帶機器轉成單帶機器，O(t) 的計算最壞變成 O(t^2)；多項式平方後仍是多項式。所以無論你是就多帶機器、單帶機器、還是理想化的隨機存取電腦來推理，P 都是同一個類別。
這種穩健性被一個工作假說捕捉，叫做 Cobham–Edmonds 論題：一個問題可行地（有效地）求解，恰恰就在它屬於 P 的時候——即可在一台確定性機器上以多項式時間求解。它是你先前遇過的邱奇–圖靈論題在時間複雜度上的表親。邱奇–圖靈說一切合理模型計算的是同一批函式；Cobham–Edmonds 再補上一句：它們彼此之間只差一個多項式的拖慢，所以「多項式對非多項式」這條界線，無論你挑哪個合理模型都落在同一處。注意這兩者都是論題而非定理——它們是關於「合理」這詞捕捉了什麼的經驗性押注，不是你能從公理證出來的東西。
正是這種模型無關性，而非帶子移動的字面記帳，賦予了 P 它的核心地位。當教科書說某問題「在 P 中」，它做的是一個能在機器模型之間、程式語言之間、以及大多數合理的「單一計算步」概念之間經受翻譯而存活的主張。這就是為什麼我們可以寬鬆地談「一個多項式時間演算法」而不必先釘死一台機器——這個類別夠穩定，細節會被洗掉。
誠實的但書：P 並不完全等於「可行」
現在來談這一階欠你的誠實，因為「P 等於可行」這句口號是個有用的理想化，不是自然律。一個帶著怪獸般常數或指數的多項式，在實務上可能毫無用處。一個以 10^100 乘以 n 步、或以 n^20 執行的演算法，技術上在 P 中，卻永遠不會在任何真實輸入上結束。某問題首個被發現的多項式時間演算法，常常糟糕地不實用，要到後來才被精煉；「在 P 中」是關於漸近成長的陳述，而大 O 刻意藏起了那些決定你等一秒還是等一世紀的常數。完整的清算見本階第 5 篇。
它也朝另一個方向切：有些最壞情況是指數的問題，在實務上天天被飛快地解開；有些真正有用的方法，甚至根本不是判定問題。P 是一條粗略而保守的線——它保證最壞情況下的良好成長，而那有時過於悲觀、有時根本問錯了問題。所以把「在 P 中」當作「問題可下手」的有力跡象，而非「某個特定實例會很快」的證書，更絕不能反過來認為「不在 P 中」就等於沒用。
最後，說一句以化解前方一個必然的混淆。下一階會引入 NP，也就是那類「提議的答案容易檢查」的問題——像一塊拼圖，難拼完，但別人把拼好的圖遞給你後卻容易核對。一個要緊的事實：P 是 NP 的子集，寫作 P 是 NP 的子集（若你能快速解，你當然能快速檢查一個聲稱的解）。而那個著名的問題——P 是否等於 NP，即每個易檢查的問題是否也易求解——是未決的。沒人證出任何一邊，而且「NP」並不意味「非多項式」。下一篇我們會把這一切理清；眼下，只要把這條線記牢：P 是「確定性、多項式時間、永遠停機的判定」所居住的地方。