自計算機科學誕生之日起——這個領域以其有條不紊地解決問題的方法而聞名——隨機性就發揮了重要作用。在世界上第一臺通用電子計算機上運行的第一個程序使用隨機性來模擬核過程。此后，類似的方法被用于天體物理學、氣候科學和經濟學。在所有這些情況下，在算法的某些步驟插入隨機數有助于研究人員解釋復雜過程可以發揮作用的多種方式的不確定性。
但是，將隨機性添加到算法中也可以幫助你計算出明確判斷真假問題的正確答案。「你只要說『好吧，讓我放棄，讓我不要嘗試，讓我隨機挑選一些東西。』」滑鐵盧大學的計算機科學家 Eric Blais 說，「對于太多的問題，這最終成為一種成功的方法。」
假設你要確定給定數字是質數（只能被 1 和它本身整除）還是合數（也可以被其他整數整除）。你可以簡單地嘗試將其除以所有可能的因數，但對于大數，這種「蠻力」方法和其他因式分解算法速度極慢。如果結果是合數，分解算法會告訴你它的除數的值——比你要求的更多的信息。如果你只關心數字的「素性」，有沒有更高效的算法？
如果你使用隨機性的話。基本思想可以追溯到 17 世紀法國數學家 Pierre de Fermat （費馬）的一個結果，即他的「小定理」。Fermat 考慮了兩個整數——稱它們為 N 和 x。他證明了如果 N 是質數，那么 x^N ? x 總是 N 的倍數，而不管 x 的值如何。等價地，如果 x^N ? x 不是 N 的倍數，則 N 不可能是質數。但逆命題并不總是正確的：如果 x^N ? x 是 N 的倍數，則 N 并不總是質數。
要將費馬小定理變成素數檢驗，只需取你感興趣的 N，隨機選擇 x，然后將這兩個數代入 x^N ? x。如果結果不是 N 的倍數，那么你就完了：你知道 N 肯定是合數。如果結果是 N 的倍數，那么 N 可能是素數。現在選擇另一個隨機 x 并重試。在大多數情況下，經過幾十次嘗試，你幾乎可以肯定地得出 N 是質數的結論。「你這樣做的次數很少。」Blais 說，「不知何故，現在你出錯的概率小于從現在到你看到答案時小行星撞擊地球的概率。」
https://www.sciencedirect.com/science/article/pii/0022314X80900840
使用隨機算法（基于對費馬小定理的改進）的第一個素數測試開創了一個新時代。事實證明，與非隨機或確定性算法相比，用隨機算法解決一個又一個問題要容易得多。關鍵是將每個問題重新定義為可以在給定某個數字 x 的適當值的情況下快速解決的問題，然后證明幾乎任何 x 都可以解決。即使研究人員不知道如何確定任何特定選擇是否是一個好的解決方案，該解決方案仍然有效。數學家開玩笑說，這個不尋常的挑戰就像大海撈針。
但這些成功讓研究人員想知道為什么隨機性應該有助于解決諸如素數測試之類的問題，這些問題都是關于尋找隱藏的、非隨機的模式。「這有點自相矛盾。」牛津大學計算機科學家 Rahul Santhanam 說， 「純粹的隨機性正在幫助你掌握解決問題的結構。」
1994 年，計算機科學家 Noam Nisan 和 Avi Wigderson 通過證明隨機性雖然有用但可能并非必需，幫助解決了這一困惑。他們證明了以下兩件事之一必須是正確的：要么所有可以使用隨機性有效解決的問題也有快速確定性算法，要么許多眾所周知的難題實際上很容易。計算機科學家認為第二種可能性極小。
https://www.sciencedirect.com/science/article/pii/S0022000005800431
事實上，計算機科學家經常發現通過從隨機版本開始然后「去隨機化」它來開發確定性算法更容易。布朗大學的計算機科學家 Eli Upfal 說：「一旦我有了它，我突然看到了一種非常明顯的方法來讓它具有確定性……但如果我不以隨機方式將其視為概率問題，我可能不會想到它。」
在 Nisan 和 Wigderson 具有里程碑意義的證明之后將近 30 年，隨機算法仍然一如既往地流行，因為去隨機化可能很棘手，而確定性算法通常僅在原則上有效。直到 2002 年，三位研究人員才找到一種去隨機化素性測試的方法，而且在實踐中，他們的算法比最好的隨機算法慢得多。對于其他問題，甚至不知道從哪里開始——最著名的算法有一個雞和蛋的問題，你只能通過隨機性來逃避。
https://annals.math.princeton.edu/2004/160-2/p12
圖論最近的突破就是這種情況。2022 年，三位計算機科學家開發了一種快速算法，用于通過圖形（由線段連接的節點網絡）找到最短路徑，即使某些線段從總路徑長度中減去而不是添加，該算法也能正常工作。他們的算法涉及通過刪除某些段將圖形轉換為更簡單的圖形，解決簡化圖形的問題，然后考慮刪除的段。他們可以證明，如果沒有最短路徑經過太多已刪除的段，算法將運行得很快——否則，最后一步將花費太長時間。
https://arxiv.org/abs/2203.03456#
但是如何決定首先刪除哪些段呢？確定性地找到理想的細分市場不僅很難——這是不可能的。該集合取決于最短的路徑，這正是三位研究人員試圖解決的問題。但即使他們找不到要刪除的最佳片段集，他們也可以證明大多數隨機選擇都很好，這足以打破自我參照循環。在極少數情況下，算法做出了一個不幸的選擇并在最后一步陷入困境，他們可以停止并再次運行它。
「隨機性基本上是一種在不知道最佳解決方案的情況下確保最佳解決方案為真的方法，」新算法的作者之一 Aaron Bernstein 說。
隨機性在計算機科學中發現了無數其他用途，從密碼學到博弈論再到機器學習。很有可能，它會留在這里。
https://www.quantamagazine.org/how-randomness-improves-algorithms-20230403/
文章來源：ScienceAI
IEEE Spectrum
《科技縱覽》
官方微信公眾平臺
