银河式算法

银河式算法（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 搜索”的单一算法，可以在渐近最佳时间内解决任何定义明确的问题。但需要注意的是，这种算法运行起来的隐藏时间复杂度常数是如此之大，以至于难以发挥什么有效作用。