Random-Number-Generator
嚴謹實用的偽隨機發生器
眾所周知，偽隨機生成器（PRG）的存在等價於單向函式的存在。反過來，後者是一個懸而未決的問題。
我很好奇是否有人開發了一種“實用的”PRG，它在計算方面比 PRG 弱，與統一隨機數生成器無法區分。
我知道一些隨機性的統計測試，但是關於這個主題有什麼嚴格的理論嗎？
這是來自 MO 的轉貼，我打算刪除原來的問題。
值得一提的是，複雜性理論中有一種聯繫，通常被稱為“Hardness v Pseudorandomness”，這使得這個問題有些困難。給定一個足夠強大的 PRG，可以使某些隨機算法去隨機化，即試圖證明 $ P = BPP $ 可以通過提供一個足夠強大的偽隨機生成器來完成。
可能令人驚訝的是，這與存在的難題密切相關。 $ NP $ . 具體來說，如果出現問題 $ NP $ 這需要指數級大小的電路，我相信這意味著 $ P = BPP $ 通過顯式偽隨機生成器的構造。此外，某種形式的反向也成立——能夠去隨機化 $ P $ （通過建構一個足夠好的參數的可證明好的 PRG）導致電路下界，這是一個眾所周知的困難主題。關鍵字是“Nisan-Wigderson PRG”之類的東西，或者您可以查看這些註釋以獲取一些提示。
我認為（但細節模糊）也可以將上述內容推廣到其他電路類，即針對某些電路類的顯式可證明安全 PRG 的存在與針對某些相關電路類的電路下限密切相關。一般來說，我們可以證明的大多數電路下限都反對相當受限的計算模型，我希望關於“嚴格 PRG”的文獻僅限於對相對較弱的計算形式安全的 PRG。
我不知道一個總結這一切的好地方 — 我自己不在該地區工作，但從做過的人那裡聽說過。也許他們的論文會是一個很好的參考，但我承認我沒有親自閱讀過它。