1樓：Bebop
通用情況方法：
列舉所有可能出現的random bits。如果本來的隨機演算法是多項式時間的，那一定不會用多於poly個數的random bits，所以可以在指數時間只能列舉所有可能的結果。如果本來的隨機演算法只用polylog個數的random bits，我們用列舉就可以有多項式時間的確定性演算法。
順便這個方法告訴我們
非構造性方法：首先我們知道通過Chernoff's inequaility 和 majority vote的，任意乙個 的隨機演算法的error rate都可以在多項式時間內被減少到 。使用the probabilistic method我們可以得到對於任意error rate 的多項式時間的隨機演算法，每個長度的inputs，都一定存在乙個一串random bits，這個random bits串可以讓每個input都走到正確答案。
所以如果我們可以找到這些random bits串，就可以有多項式時間的確定性演算法。
非確定性：如果說之前的兩種方法還可以讓人看到希望的話，這種方法更加只存在於理論中。首先很明顯 。
但是我們並不清楚 和 之間的包含關係，不過我們可以認為非確定性是要比隨機性更強的，因為不難證明如果 。
對於一些具體的問題，會有針對具體問題的具體方法，例如derandomizing MaxCut可以在每一步bound exception value來得到乙個貪婪演算法，或者因為MaxCut只要求random bits是pair-wise independent的，我們可以用log數量的random bits來構造poly個數的pair-wise independent random bits。再使用列舉方法來列舉所有的random bits，就可以完成對於MaxCut問題的去隨機化。
以上內容全部抄書自Pseudorandomness
2樓：Bubbles
可參考lecture note Psuedorandomness 第三章，這是經典文獻。http://
people.seas.harvard.edu
/~salil/pseudorandomness/
電腦取隨機數是什麼原理，是真正的隨機數嗎？
想吃沙茶面 偽隨機數 以python random 包為例 預設的random 返回在0.0 x 1.0範圍內 2 的倍數。所有這些數值間隔相等並能精確表示為 Python 浮點數。但是在此間隔上有許多其他可表示浮點數是不可能的選擇。例如，0.05954861408025609就不是 2 的整數倍。...
不確定原理能說明因果是隨機的嗎
我是腦殘窩囊廢 若無因而有萬物者。是則為常。是事不然。無因則無果。若無因有果者。布施持戒等應墮地獄。十惡五逆應當生天。以無因故。問 無因有幾種?答 有二種 一者計無有於因,故名無因。二者計有因是無因。如初章雲 有有可有,有是自有,故不因無也。破無因事有四過 一常過。二理奪。三反並。四倒感果。常過者,...
Mathematica的Part原理是什麼？
Mathematica中有一句老話 everything is an expression.什麼意思呢？就是字面意思啦 從列表裡面取內容OP應該會，不就是 1 麼 那麼下一步就到了題主的問題，到底這是怎麼取得呢？其實，mma在kernel裡面會先把這個表示式翻譯成為Part List a,b,c,d...