上一篇遺留下來的一個顧慮
上一篇我們把 P 類釘死了：它是一台圖靈機能在多項式時間內解出的判定問題，其執行時間最多是輸入長度的某個固定次方，例如 O(n^2) 或 O(n^3)。這是個乾淨的定義。但細心的讀者該感到一根小刺般的疑慮。整個定義懸掛在一個非常特定的小裝置上——單一一條帶子、一個讀寫頭、一次一格地把符號搬來搬去。那是一台被刻意弄得貧乏的機器。為什麼「有效率」的界線，要取決於這麼一個古雅的玩意兒？
把這個顧慮說得鋒利些。假設我在一台有好幾條帶子的機器上，用 O(n^2) 步解出了某個問題，於是每個子任務都有自己的草稿空間。如果我現在必須把所有這些工作擠到單一一條帶子上——付出代價讓讀寫頭在原本是不同帶子的區域之間來回走動——我的步數可能會暴增。它會暴增到足以把這問題推出多項式時間之外嗎？若會，那麼 P 就是硬體的一個偶然：換台機器，這一類就變了，「P」也就不帶任何絕對的意義。若不會，那麼 P 就是問題本身的性質，而非機器的性質。這一篇要做的，就是誠實地確立：答案是「不會」。
多帶歸於一帶：是多項式減速，而非爆炸
從最廉價的升級開始：一台多帶圖靈機，它不過是一台普通機器被配給了 k 條各自獨立的帶子，每條都有自己的讀寫頭，且全都在同一步裡移動。標準定理說：一台單帶機器能模擬一台 k 帶機器，而代價是溫和的：若這台多帶機器跑了 t 步，單帶的模擬就跑 O(t^2) 步。是平方，不是指數。那個平方，正是強迫許多工作區域共用一條帶子所付的價——但一個多項式的平方仍然是多項式，所以被模擬的機器仍留在 P 之內。
這機制值得想像一番，因為那個 O(t^2) 的界並非魔法。把 k 條帶子並排放到一條長帶上，以交錯的軌道排列，並用一個特殊的點標出每個讀寫頭當前的位置。為了模擬多帶機器的一步，單帶讀寫頭做一次橫越所有標記區域的完整掃描，以讀出每個虛擬讀寫頭底下的符號，再做第二次掃描來更新每一個並移動那些點。關鍵在於：t 步之後，用到的區域大約可達 t 格寬，所以每次掃描要花 O(t)。要模擬 t 步、每步花 O(t)，總計就是 O(t^2)。這個減速是實實在在的，但它被原本時間的一個多項式所界定，而這恰恰就是我們想要的保證。
Multi-tape machine, one step: Single-tape simulation of that step:
tape1: . . a [b] c . ...sweep RIGHT across all tracks...
tape2: . [x] y . . . read symbol under each * (the heads)
tape3: . . . [z] . . ...sweep LEFT, update + move each *...
^each [.] is a head cost per simulated step = O(t)
steps to simulate = t
one parallel step -----------> total single-tape cost = O(t^2)
Square of a polynomial is still a polynomial => stays in P.那真實的電腦呢？RAM 模型
一台帶子機器，看起來仍然完全不像你桌上的筆電——筆電能在一條指令裡跳到任何記憶體格子，不必把讀寫頭橫越整條帶子搬來搬去。這就是隨機存取機器（random-access machine, RAM），是真實硬體與一般虛擬碼真正相符的那個理想化模型。這台肯定更強，能在多項式時間內解出圖靈機解不了的東西吧？就純粹的可計算性而言，不：RAM 與圖靈機判定的恰是同一批語言。就時間而言，答案才是這裡要緊的那個——圖靈機能以僅僅多項式的減速模擬一台 RAM（反之亦然），所以這兩個模型定義出的，是完完全全同一個 P 類。
這個模擬雙向都行得通，而看清為何如此，能讓你對一個微妙的陷阱保持誠實。一台圖靈機在模仿 RAM 時，把 RAM 的記憶體存成帶子上的一串「（位址，值）」配對；一次隨機存取就變成一趟掃描去找出正確的位址，其代價是目前為止已做工作量的一個多項式，而非常數。反方向走，一台 RAM 模仿圖靈機，只要把帶子放進一個陣列、再追蹤讀寫頭的索引即可——很便宜。那個微妙的陷阱是：這一切都仰賴 RAM 使用合理大小的數。若你容許單一一個記憶體格子裝下一個天文數字般大的整數，並在「一步」內把兩個這樣的巨數相乘，你就偷渡進了不切實際的能力，而多項式等價就垮了。誠實的模型會對大數收費；有了那份公平的計帳，P 就被保住了。
讓「P」成為一個真詞的那條論題
退一步，讀出這個模式。多帶歸於單帶：多項式。RAM 歸於圖靈機：多項式。對暫存器機器、對二維帶子、對幾乎任何你能想出的合理串列電腦，同樣成立——每一個都能以至多多項式的時間膨脹模擬其他的。由於多項式對複合封閉（多項式的多項式仍是多項式），把這些模擬串接起來，永遠逃不出多項式時間。所以你得到的這一類，在它們全體之間都是同一個。這個經驗性卻很牢固的觀察有個名字：Cobham–Edmonds 論題，它主張「在一台確定型機器上多項式時間內可解」是「原則上有效率可解」的正確形式替身，正因為它不取決於你選了哪台合理的機器。
這正是 P 配得上一個大寫字母、而像「在 2 帶機器上 O(n^3)」這樣的具體界配不上的深層理由。確切的指數的確是取決於模型的——從多帶換到單帶可以把它平方，把一個 O(n^2) 演算法變成 O(n^4)——但「指數是某個常數」這個赤裸裸的事實，是與模型無關的。P 的模型無關性意味著，我們可以談論一個問題屬於 P，而完全不必指名任何機器，就像我們談論一個數是質數時，不必指名任何記數系統一樣。這個歸屬，是問題內在的性質。
穩健性止步之處：誠實的附帶細則
模型無關性是一份強大的禮物，但它並非無條件的，假裝它無條件，恰恰會是本課程拒絕的那種令人安心的謊言。論題悄悄地說的是「每個合理的模型」，而「合理」這個詞是承重的。有兩個著名的「逃生口」，在那裡多項式模擬的保證並不為人所知是否成立，而它們正是整門學科裡最有趣的對象。
第一個是非確定性。一台非確定型機器——那個拼圖模型，被允許先猜、再驗證——並不被相信能由一台確定型機器以僅僅多項式的減速來模擬。我們所知最好的一般性模擬是指數的。多項式的模擬是否存在，恰恰就是 P 對 NP 的問題，是本領域核心的未解難題。所以非確定性被刻意留在那批「對 P 有共識的合理串列模型」之外；它或許是、或許不是另一種怪獸，而沒有人證明過究竟是哪一種。
第二個是量子計算。一台量子電腦是一個真正不同的物理模型，而那個強主張——每一台物理上可實現的裝置都能以僅僅多項式的減速模擬圖靈機——就是擴展 Church–Turing 論題，而量子計算正是懷疑它的首要理由。有些問題，因數分解是著名的一個，已知有多項式時間的量子演算法，卻沒有已知的多項式時間古典演算法。不過要誠實地提兩點警告：這關乎一個可能超過多項式的減速，而非計算任何先前不可計算的東西；而且儘管標題寫得隨便，一台量子電腦並不被認為能有效率地解 NP 完全問題。P 的穩健性是真實且承重的——但它是一個關於合理串列模型的主張，而以上這兩道著名的前沿，被誠實地隔在了外面。