BPP（有界錯誤機率多項式時間）
想像一個演算法在執行時可以擲硬幣，大部分情況下會給你正確的是非答案，但在任何一次執行裡都有一點點出錯的機率。這聽起來很危險，卻正是許多又快又實用的演算法所提供的條件。BPP 就是用這種方式可解的問題的正式歸宿：由一個在多項式時間內執行、使用隨機位元、並且對每個輸入都以高機率答對的演算法來解。
精確地說，一個決定問題屬於 BPP，是指存在一個使用隨機擲硬幣的多項式時間演算法，使得對每個輸入，它答對的機率至少是 2/3（答錯至多 1/3）。這個 2/3 並不神奇：因為各次獨立執行的錯誤彼此獨立，你可以把演算法跑很多次再取多數決，多數決出錯的機率就會以天文般的速度縮小。跑個幾百次，失敗機率就低於宇宙射線翻轉你電腦裡某個位元的機率。於是「通常答對」便廉價地變成「對所有實際用途而言都答對」。
BPP 捕捉了「只要願意接受一個極微小、可控的錯誤就算高效」這個想法。顯然 P（確定型多項式時間問題）落在 BPP 之內，因為從不擲硬幣的演算法只是一個特例。最深刻而優美的驚奇——在「去隨機化」條目討論——是複雜度理論家如今普遍相信 P = BPP：對決定問題而言，隨機性基本上買不到額外的計算能力，只是有時帶來更簡單或更快的演算法。這個信念至今仍是猜想，而非定理。
數十年來最快的實用質數判定法是隨機化的（Miller-Rabin）：要判定 n 是否為質數，隨機挑一個 a，跑一個快速檢驗看 a 是否「見證」n 為合數；真正的質數永遠通過，而合數對大多數 a 都會失敗，所以用新的隨機 a 重複，便使誤判為「質數」的機率呈指數遞減。因此 PRIMES 輕易屬於 BPP——後來更被證明根本就屬於 P。
BPP 演算法擲硬幣、通常答對，而多數決能把它的錯誤推向零。
BPP 的錯誤必須對每個輸入都遠離 1/2（名稱裡的「有界錯誤」）；一個只在 50.0001% 的時候答對、而且這個差距隨輸入增大而縮小的演算法並不合格，因為靠投票放大正確率已不再廉價有效。