為什麼計算機科學家會諮詢預言機
原文：https://www.quantamagazine.org/why-computer-scientists-consult-oracles-20250103
作者：Ben Brubaker
譯者：Kurt Pan
能夠快速且準確回答問題的假想裝置已成為計算複雜性理論中的一個強大工具。
向神奇八號球提出一個問題，它會回答「是」、「否」或是惱人的不確定。我們將它視為孩子的玩具，但理論計算機科學家卻在使用類似的工具。他們常常想像自己能諮詢稱為「預言機」的假想裝置，這些裝置可以即時且正確地回答特定問題。這些富有幻想的思維實驗啟發了新的算法，並幫助研究人員繪製了關於計算的地形圖。
調用預言機的研究人員屬於計算機科學的一個子領域，稱為計算複雜性理論。他們關注的是問題的內稟難度，例如判斷一個數是否為質數，或是在網絡中找到兩點之間的最短路徑。有些問題容易解決，另一些看似更難但有易於檢查的解，還有一些對量子電腦而言容易，但對普通電腦來說似乎很難。
複雜性理論學者希望理解這些表面上的難度差異是否是根本性的。某些問題是否本質上困難，還是我們只是不夠聰明，無法想出好的解決方案？研究人員通過將問題分類到「複雜性類」中來解決這些問題——例如，所有容易的問題放在一個類，所有易於檢查的問題放在另一個類——並證明這些類之間關係的定理。
不幸的是，事實證明繪製計算難度的地形圖本身，是——嗯——困難的。因此在1970年代中期，一些研究人員開始研究如果計算規則不同會發生什麼情況。這就是預言機派上用場的地方。
像神奇八號球一樣，預言機是立即回答是否問題的裝置，而不會透露其內部運作的任何信息。與神奇八號球不同的是，預言機總是回答「是」或「否」，而且總是正確的——這是它作為虛構裝置的一個優點。此外，任何特定的預言機只會回答特定類型的問題，例如「這個數是質數嗎？」
這些虛構裝置為理解現實世界帶來了什麼樣的幫助？簡而言之，它們能揭示不同複雜性類之間隱藏的聯繫。
以兩個最著名的複雜性類為例。首先是研究人員稱為「P」的容易解決的問題類，其次是研究人員稱為「NP」的容易檢查的問題類。所有容易檢查的問題也都是容易解決的嗎？如果是這樣，這將意味著 NP 等於 P，所有加密都將變得容易破解（以及還有其他後果）。複雜性理論學家懷疑 NP 不等於 P，但他們無法證明這一點，儘管他們已經嘗試來確定這兩個類之間的關係超過 50 年。
預言機可以幫助他們更好地理解所處的情境。研究人員發明了能回答有助於解決許多不同問題的預言機。在一個每台電腦都能連接到這些預言機之一的世界中，所有容易檢查的問題也將變得容易解決，P 將等於 NP。但其他較不有用的預言機則產生相反的效果。在這些預言機充斥的世界中，P 和 NP 將被證明是不同的。
研究人員利用這些知識更好地掌握了 P 與 NP 問題。最初試圖確定 P 和 NP 之間關係的嘗試使用了一種稱為對角化的優雅技巧，這個技巧在計算機科學的其他重大成果中也至關重要。但研究人員很快意識到，任何基於對角化的證明也適用於任何電腦都能諮詢相同預言機的世界。這預示著災難，因為預言機會改變 P 與 NP 問題的答案。如果研究人員能夠使用對角化來證明在現實世界中 P 和 NP 是不同的，則同樣的證明將意味著在一個充滿預言機的世界中 P 和 NP 是不同的，但在那個世界中它們顯然是相同的。這意味著任何基於對角化的 P 與 NP 問題解決方案都將是自相矛盾的。研究人員因此得出結論，他們需要新的技術來取得進展。
預言機對量子計算的研究也有幫助。在1980年代和1990年代，研究人員發現了利用量子物理來快速解決某些對普通「經典」計算機來說看似困難的問題的方法。但這些問題只是看起來困難，還是真正困難？要證明其中一種情況需要徹底嶄新的數學技術。
因此，研究人員研究了量子電腦在涉及預言機的問題上的表現。這些努力可以間接證明量子電腦確實比經典計算機更強大，並且可以幫助研究人員探索量子電腦可能擅長的本質上的新任務。有時，它們甚至可以有實際應用。1994年，應用數學家彼得·肖爾受到最近一項預言機結果的啟發，開發了一種快速的量子算法來因式分解大整數——該任務的困難性是我們在線數據安全加密系統的基礎。肖爾的發現引發了一場建造強大量子電腦的競賽，這場競賽一直持續到今天。
很難預測複雜性理論的未來，但並非關於該領域發展軌跡的每個問題都同樣難以回答。研究人員會繼續諮詢預言機嗎？跡象表明會的。