去隨機化（derandomization）

假設你有一個美妙簡單的演算法，它之所以可行，只因為它擲了真正的硬幣。一個自然、近乎貪心的問題隨之而來：你真的需要貨真價實的隨機性嗎？還是能用某種確定性的東西替換那些硬幣，仍然保持正確？去隨機化就是這個計畫：在不損失效率的前提下，從隨機化演算法中移除隨機性——把一個擲硬幣（BPP 式）的演算法變成在多項式時間內執行的普通確定型演算法。

這個計畫的核心引擎是偽隨機產生器：一個確定型的程序，把一段很短的真隨機種子拉伸成一長串「看起來隨機」的位元——意思是任何高效演算法都無法把拉伸出的位元和真正的擲硬幣區分開來。若這樣的產生器存在且本身高效，你就能把它的輸出餵給你的隨機化演算法以取代真硬幣並得到相同答案，然後確定性地掃過所有可能的短種子。這條研究路線（Impagliazzo 與 Wigderson 等人）令人震驚的結果是有條件卻醒目的：若 EXP 裡的某個問題真的需要指數規模的電路——一個非常可信的困難性假設——那麼好的偽隨機產生器就存在，因此 P = BPP。一句口號：困難性產生隨機性；困難問題的存在讓我們能完美地偽造隨機性。

這正是複雜度理論家壓倒性地相信 P = BPP（隨機性對多項式時間的決定無增益）的原因，儘管它仍未被證明。這個信念翻轉了一個曾經自然的直覺：人們長久以來假設隨機性是一種額外資源，但現在它看起來像一種我們原則上可以捨棄的便利。要誠實地附帶幾點：這是一個建立在電路困難性假設上的猜想，它關乎決定問題與最壞情況效率（不一定是相同的常數因子或同等的優雅），而且它並不主張隨機性在密碼學或抽樣中無用——在那些場合，它扮演著另一種不可或缺的角色。