一台會擲硬幣的機器
到目前為止你遇過的每一台機器都是可預測的：把同一個輸入餵給一台圖靈機兩次，它兩次都做完全相同的事，因為每一步動作都由規則 delta(q, a) = p 固定下來。這一階梯一開始就遞給那台機器一個新道具——一枚公正的硬幣。在任何一步，它都可以擲硬幣並依結果分岔：正面做這個，反面做那個。這台機器仍然是一台誠實的、一步一步來的電腦，有有限的控制器和一條紙帶；它只是多了一條真正隨機的位元流可用。我們稱它為機率型機器，而本篇的問題很直接：讓一台機器去賭博，真的能讓它把問題解得更快嗎？
千萬別把這種擲硬幣和前面階梯的非確定性搞混。當一台 NFA 或一台非確定型圖靈機面對一個選擇時，它在概念上會把自己複製出來並同時探索每一條分支，只要任一分支接受就接受——那是一個完美、神奇、毫無「可能性」概念的猜測者。一台機率型機器並沒有一支分身大軍。它只走一條路徑，每個岔路口都靠一次真實的擲硬幣來選，而要緊的量是這唯一一趟運行落在正確答案上的機率。正如詞彙表所強調的，非確定性不是隨機性：非確定性問的是「是否存在一條幸運的路徑？」，而隨機性問的是「一條路徑是否很可能？」。這是兩個非常不同的問題，它們定義出非常不同的類別。
把「有界誤差」講精確：BPP
回想 P 類：確定型機器能在多項式時間內判定的是/否問題，是我們對「能有效且精確求解」的實用代稱。它的隨機版本是 BPP，意思是「有界誤差機率型多項式時間」（Bounded-error Probabilistic Polynomial time）。一個問題若存在某台多項式時間執行的機率型機器，且在每一個輸入上都以至少 2/3 的機率給出正確的是/否答案，那它就在 BPP 中。「以至少 2/3 的機率」這句話就是全部關鍵：這台機器被允許出錯，但只能以一個有界、且嚴格優於擲硬幣的機率出錯，而且要在每一個輸入上都如此——不只是在大多數輸入上。
為什麼偏偏是 2/3 這個怪數字？因為那個確切的常數幾乎無關緊要，而這正是漂亮之處。任何固定地大於 1/2 的差距都行得通——0.51、2/3、0.9 定義出的是同一個類——這要歸功於機率放大。把這台機器在同一個輸入上跑很多次，再對所有答案取多數決。每一趟都是一場由硬幣驅動、偏向真相的獨立試驗，所以依大數法則，多數那一邊壓倒性地很可能是對的。寥寥幾趟獨立運行就已把誤差從 1/3 壓到百分之幾；幾百趟就把它壓到比你的電腦在計算途中被隕石擊中還低。關鍵在於，要達到任何目標信心水準所需的重複次數是一個常數（或頂多溫和地增長），所以多項式時間仍是多項式。這正是我們之所以能容忍一台擲硬幣機器偶爾出錯的原因：誤差不是一個固定的缺陷，而是一個旋鈕，我們能以一筆不大的、多項式的代價把它轉到我們想要的任何低點。
單邊與零邊：RP 與 ZPP
BPP 允許機器在兩個方向上出錯——一個真正的「是」可能被誤報成「否」，反之亦然。我們往往能做得更好。RP 類（隨機型多項式時間，Randomized Polynomial time）是單邊版本：當真正的答案是否時，機器絕不出錯——它一定說「否」；當真正的答案是是時，它以至少 1/2 的機率說「是」，但有時可能錯誤地說「否」。這正是一場隨機尋找見證者的天然形狀：單單喊一聲「是」是可信的，因為機器無法捏造出一個假的「是」；而喊一聲「否」也許只是壞運氣，多試幾次就能翻盤。
更好的是 ZPP（零誤差機率型多項式時間，Zero-error Probabilistic Polynomial time），也就是 Las Vegas（拉斯維加斯）演算法的家：答案總是正確，只有執行時間是隨機的。想像一個演算法不斷抽取隨機猜測，直到抽到一個可被驗證為正確的——它的輸出絕不出錯，但你無法保證它確切何時完成，只能保證它平均而言很快完成。把這拿來和 BPP 與 RP 的 Monte Carlo（蒙地卡羅）風格對比：那裡執行時間是固定的，但答案可能出錯。一句乾淨的心法口訣：拉斯維加斯永遠說真話，但花的時間不確定；蒙地卡羅永遠準時收工，但可能稍微撒個謊。這些類別乾淨地層層相套：ZPP 在 RP 之內，RP 在 BPP 之內，而每一個確定型 P 演算法都理所當然地算作一個忽略自己硬幣的隨機演算法，所以 P 在它們全部之內。
WORST-CASE BEHAVIOUR ON A SINGLE RUN class true=YES true=NO time ----- ----------------- ----------------- -------------- P always YES always NO fixed, poly ZPP always YES always NO random, poly avg (Las Vegas) RP YES w.p. >= 1/2 ALWAYS NO fixed, poly (Monte Carlo, 1-sided) BPP YES w.p. >= 2/3 NO w.p. >= 2/3 fixed, poly (Monte Carlo, 2-sided) nesting: P in ZPP in RP in BPP amplify any of them: repeat + vote -> error shrinks fast, time stays poly
BPP 在地圖上坐落何處？
該把 BPP 放到你一直在建構的那張複雜度類別地圖上了。我們知道 P 在 BPP 之內，因為硬幣是一個你可以拒絕使用的選項。另一端，BPP 被包含在 PSPACE 之內：一台多項式空間的機器原則上可以一次一條地遍歷所有可能的擲硬幣序列，重複利用同一塊草稿空間，並統計答案為「是」的次數有多頻繁——把機率變成一個精確的計數。於是我們有 P 在 BPP 之內，BPP 又在 PSPACE 之內。但 BPP 相對於 NP 坐落何處，則真的曖昧不明：BPP 並未已知在 NP 之內，NP 也未知在 BPP 之內。隨機擲硬幣者和幸運猜測者是兩種不同的野獸，而它們如何比較仍是未解。
現在輪到那個幾乎讓所有人都吃驚的轉折。數十年來，隨機性看起來像是一項貨真價實的額外資源：某些問題有快速的隨機演算法，卻沒有已知的確定型演算法。旗艦案例是質數判定——判斷一個數是否為質數——其中著名的 Miller-Rabin 擲硬幣測試把任何確定型方法遠遠甩在後頭。那麼 BPP 想必嚴格大於 P 囉？驚奇來了：2002 年，AKS 演算法把質數判定不靠任何硬幣地穩穩放進了 P，抹掉了那道最著名的鴻溝。而今日複雜度理論家之間更廣泛的信念甚至更大膽：多數人猜想 P 等於 BPP——也就是說，對於判定問題而言，隨機性買到了速度和簡潔，卻買不到根本上的力量。若此為真，每一個 BPP 演算法原則上都能被改造成確定型的。
去隨機化：用難度換取硬幣
那個立志要證明 P 等於 BPP 的研究計畫，叫做 去隨機化：在保持演算法高效的同時，有系統地把隨機演算法裡的硬幣移除。核心工具是一個偽隨機產生器——一個確定型的小道具，能把一顆極小的、真正隨機的種子，拉伸成一條長長的位元流，而任何高效演算法都無法把它和真正的擲硬幣區分開來。若這樣的產生器存在，你就能把一台 BPP 機器昂貴的隨機性換成一顆便宜的種子，接著確定型地遍歷所有可能的短種子，再取多數決。隨機性消失了；答案存活了下來。
- 從一個 BPP 演算法 M 出發，它在輸入 x 上擲 m 個隨機位元，並以至少 2/3 的機率正確作答。
- 假設我們擁有一個偽隨機產生器 G，它能把一顆長度為 s 的短種子（s 遠小於 m）變成 m 個位元，而 M 無法將它們和真正的隨機位元區分開來。
- 由於 M 無法把 G 的輸出和真正的硬幣區分開來，把 M 跑在 G 的位元上，所得到的答案機率本質上就和把它跑在真正的硬幣上一樣。
- 現在施展那個確定型的把戲：遍歷全部 2^s 顆短種子，用每一顆各跑一次 M，並輸出多數那一邊的答案——完全不用硬幣，而當 s 對輸入大小取對數時，2^s 仍然很小（多項式）。
- 結果是一個確定型、多項式時間、答案相同的演算法——那個隨機問題已被推進了 P 之中。
那麼這樣的偽隨機產生器到底存不存在？這裡藏著現代複雜度理論中最美的一條線索：一系列深刻的結果（所謂的「難度對隨機性」連結）顯示，夠強的計算難度，蘊含夠強的去隨機化。具體地說，若 EXP 中某個問題真的需要指數規模的電路——這是多數理論家所相信的一個難度假設——那麼好的偽隨機產生器就存在，而 P 等於 BPP 隨之成立。這句口號很驚人：若難題真的難，那麼對判定問題而言隨機性毫無用處。但這是一個蘊含關係，而非關於現實的定理——它立足於一個未經證明的難度假設。P 是否真的等於 BPP，仍是這個領域的重大未解問題之一，與 P 對 NP 織進同一塊布料裡。