RP 與 ZPP（單向錯誤與零錯誤隨機類別）
並非每個擲硬幣的演算法都犯同一種錯。RP 與 ZPP 是對「隨機演算法」這個想法的兩種細緻精煉，靠的正是「它究竟如何、以及是否曾被允許說謊」來區分。想像兩種偵探：一種從不誣陷無辜，但有時會放走真兇（單向錯誤）；另一種完全不出錯，卻無法保證調查確切要花多久（零錯誤，隨機時間）。
RP（隨機化多項式時間）是那位單向偵探。若真實答案是「否」，RP 演算法永遠說「否」；若真實答案是「是」，它以至少 1/2 的機率說「是」（也可能錯說「否」）。所以 RP 演算法給的「是」是金科玉律——它真的找到了某個見證——而「否」可能是漏失，你可以重新檢驗。ZPP（零錯誤機率多項式時間）是那位永不出錯的偵探：它永遠回傳正確答案，但執行時間是隨機的，僅在平均意義下為多項式。這些就是「拉斯維加斯」演算法（永遠正確，賭時間），相對於「蒙地卡羅」演算法（時間固定，賭正確性）。
它們之間的關係乾淨俐落，值得記住。ZPP 等於 RP 交 co-RP：一個問題擁有永不出錯、期望多項式的演算法，正好等同於它與它的補集都擁有單向錯誤的演算法——你同時跑兩者，直到其中一個確定地說「是」。而 RP 落在 BPP 之內，因為單向錯誤是有界雙向錯誤的特例。P 落在它們全部之內。和 BPP 一樣，這些類別是否嚴格大於 P 仍未解，而主流信念——透過去隨機化——是它們全都塌縮回 P。
判定一個龐大的符號多項式是否恆等於零，是個經典的 RP 問題：代入隨機數字求值；若多項式真的恆為零，它必定算出零（絕不會誤判為「非零」），而若它非零，隨機點以高機率使它非零，所以「非零」的判決可信，而「零」的判決可以再檢查。
RP 絕不給出假的「是」（單向錯誤）；ZPP 完全不出錯，卻在執行時間上賭一把。
蒙地卡羅（固定時間、可能出錯）與拉斯維加斯（永遠正確、隨機時間）並非「較好」與「較差」的行話——它們是不同的保證。把拉斯維加斯演算法在時間預算用盡時切斷，便能轉成蒙地卡羅演算法，用一點小錯誤換取一個硬性截止時限。