銀河式算法

銀河式算法（Galactic Algorithm）不是某一種具體算法的名稱，而是一類對於極大規模數據表現特別優異的複雜算法。這類算法在常規問題中往往無法展現出優勢，甚至效率低於一般的解決方案，而當數據規模足夠大時，效率將提升到不可思議的程度。這裏的「足夠大」實際上已經脫離了現實需求，以至於這類算法從未在實踐中發揮作用。「銀河式算法」一詞首先由理查德·立普頓和肯·里根提出，「銀河式」意味着面對數據規模之大如銀河中的繁星，且「不會與地球上的問題打交道」。

銀河式算法的著名示例包括一種大整數乘法，其基於 $1729$ 維的快速傅里葉變換。這意味着只有當數值至少達到 $2^{1729^{12}}$ （即 $10^{10^{38}}$）位十進制數字之後,這種算法的優勢才能發揮出來，而這個數量級已經遠遠超過宇宙中原子的數量，因此這種算法從未被真正使用過。

即便銀河式算法看起來沒有用處，但有關這類算法的思想和討論仍然對計算機科學大有裨益。

• 一種看似不切實際的算法所展現出來的新技術，可能會最終轉變為比當下更好的實用算法。
• 計算機的高速發展可能會使解決一些原本不曾邂逅的大規模問題變得迫在眉睫，算力和存儲空間的提升可能會為一些原本難以實施的複雜算法提供實踐機會。
• 不切實際的算法會證明或證偽當下一些猜想的邊界。據立普頓所說，「這一點非常重要，並且通常是我們找到此類算法的重要原因。例如，如果明天發現一個因式分解算法具有巨大但可證明的多項式時間複雜度，即使我們深信該算法可能永遠不會使用，但仍會影響我們未來對於因式分解相關技術的研究，為更新穎、更可靠的想法提供經驗。」同樣，一種用於解決布爾可滿足性問題的、時間複雜度為 $O\left(n^{2^{100}}\right)$ 的算法雖然在實踐中不可用，但仍然有益於人們探索P=NP問題——這一計算機科學中最重要的開放性問題，也是千禧年大獎問題之一。

範例

有幾種眾所周知的算法具有無與倫比的漸近行為，但僅針對難以想像的極大規模問題：

• 矩陣乘法：第一次將 $O(N^{3})$ 的暴力算法改進到 $O(N^{2.807})$ 的是施特拉森算法，這是一種遞歸算法。它的確曾在實踐中被使用過，嚴格來說並不屬於銀河式算法。庫珀史密斯-溫諾格勒算法在其基礎上利用複雜的群論進一步改進，使時間複雜度降低到 $O(N^{2.373})$。而這是「銀河式」的——「儘管如此，我們強調這樣的改進僅在理論上有意義，因為快速矩陣乘法的複雜性所涉及的巨大常數使這些算法不切實際。」
• 克勞德·香農提出了一種簡單但只在理論中可行的程序。它需要對每一個可能的、長度為 N 比特的信息標記一個隨機編碼，接着通過尋找最近的編碼進行譯讀。如果 N 被取得足夠大，它將會勝過任意現存編碼，並任意接近信道容量。不幸的是，任何能夠大於現存編碼的 N 是不現實的。儘管這些編碼從未被使用，卻激發了數十年來隊更實用的算法的研究。這些算法如今可以達到任意接近信道容量的速率。
• 在圖論中，確定圖 G 是否包含圖子式 H ，通常是一個NP-完全的問題。但當 H 固定時，該問題可以在多項式時間內得到解決。測試 H 是否為 G 的圖子式，在這裏有着 $O(n^{2})$ 的複雜度，此處 n 是 G 所包含頂點的數量，且大O記號的常數是以超指數的（superexponential）增長趨勢依賴 H。這個常數大於 $c>2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))$ （此處利用高德納箭號表示法），其中 h 是 $H$ 的頂點數。
• 對於密碼學家來說，「找鑰匙開鎖」比暴力攻擊要快得多，即對序列中的每個可能的密鑰嘗試一次解密操作。即使這些方法往往廣為人知，但對於當下技術水平而言仍然是行不通的。最好情況下，攻破 $128$ 位 AES 算法僅需 $2^{126}$ 次攻擊。儘管尚無法實際實踐，但理論上的突破有時可以提供對漏洞模式的深入了解。
• 存在一種被稱為「Hutter 搜索」的單一算法，可以在漸近最佳時間內解決任何定義明確的問題。但需要注意的是，這種算法運行起來的隱藏時間複雜度常數是如此之大，以至於難以發揮什麼有效作用。