借来一块装满的硬盘，计算机就能更快

有些问题耗时少但很吃内存，另一些则正好相反。对于少数几个基本任务，理论学家已经证明了这种权衡存在硬性极限：工作内存很小时，就不可能很快。一篇新论文表明，一种奇特的资源，即一块已经装满、且必须原样归还的内存，能够打破这些极限。

借来的硬盘

这一模型称为催化计算（catalytic computing），由Buhrman、Cleve、Koucký、Loff和Speelman于2014年提出。算法拥有一块很小的干净内存，对于规模为n的输入，大小约为log n比特；另外还有一块巨大的脏内存，里面已经填满了它无法选择的任意数据。它可以随意使用两者，但在停止时，脏内存的每一个比特都必须和原来一模一样。

作者使用了标准的比喻：你借来朋友的一块巨大硬盘，里面装满了珍贵的数字记忆，用来运行一次计算。你不想失去这位朋友，所以用完后会把每个比特都恢复原样。

这个模型最初是想证明这样的内存毫无用处。直觉上，要恢复一切，就必须保留全部信息，因此永远腾不出任何空间。令人意外的是，事实恰恰相反：装满的内存能让人解决一些没人知道如何只用干净内存解决的问题。但这些结果针对的是空间，而且算法极其缓慢。

比可证明的极限更快

麻省理工学院的Adelmo Morrison Orozco、Nathan Sheffield和Ryan Williams这次关注的是速度。在对数级干净内存和多项式规模借用内存的条件下，他们给出的算法能够：

• 在n^(1+o(1))时间内，即几乎线性的时间内，对列表排序并计算离散傅里叶变换；
• 在n^(ω+o(1))时间内完成矩阵乘法，与内存不受限时已知最好的方法一样快。

没有借来的硬盘时，已经证明：对于排序和傅里叶变换，时间与内存的乘积至少为n²量级；对于矩阵乘法，至少为n³量级。因此，这些催化算法达到了任何普通小内存算法都无法达到的速度。作者称，这是首次无条件地证明催化算法胜过非催化算法。

切换、读取、撤销

关键要素是一个简短的组合技巧。假设算法可以让借来内存中的某一段在一个未知值τ和τ + x之间切换，其中x是它关心的结果。在一张同样是借来的大“辅助”表中，给一组精心挑选的条目各加1。位置τ处的条目增加1，当且仅当x属于某个给定集合。然后把每一步倒着执行一遍，硬盘就恢复原状，只留下你想要的那一比特答案。

把这个技巧逐层叠加，就能快速计算浅层电路。作者随后把排序网络、快速傅里叶变换和快速矩阵乘法都改写成这样的电路。在算术运算中，只有把两个未知量相乘的层需要额外代价；纯线性层几乎是免费的。

公平的比较

一个反对意见是：经典极限假设答案只写一次，从左到右写在一条单独的输出带上，而催化算法则把答案写进借来的硬盘里。论文回应了这一点。作者证明，他们的算法可以在输出带上分两遍写出答案，而对普通算法来说，两遍并不比一遍更有帮助。因此这些极限依然适用，分离结果成立。他们还证明，即使有借来的硬盘，一遍也不够：此时排序会撞上同样的n²壁垒。

一长串受益者

同样的工具还给出了一系列快速催化算法：大整数和多项式乘法、网络中的三角形计数和团（clique）查找、路径和环检测，以及带通配符的文本模式匹配。它们的运行时间在小因子范围内与拥有任意内存的已知最佳算法相当。在每种情况下，借来的内存仍必须完全按照借出时的样子归还。