摘要：MIT 的 Ryan Williams，刚刚打破了一个沉睡半世纪的难题。50 年来，理论计算机科学界都认为，在空间复杂度这事上，Hopcroft、Paul 和 Valiant 的结果已经是极限。也就是说，用更少的内存去跑所有类型的算法，是不可能的。

MIT 的 Ryan Williams，刚刚打破了一个沉睡半世纪的难题。50 年来，理论计算机科学界都认为，在空间复杂度这事上，Hopcroft、Paul 和 Valiant 的结果已经是极限。也就是说，用更少的内存去跑所有类型的算法，是不可能的。

他们错了。

Williams 发现了一种新模拟方法，能把任何时间复杂度为 T 的算法，转化成一个空间复杂度只有 √T 的版本。虽然速度会慢很多，但在理论上，这彻底改变了时间与空间的权衡逻辑。

核心点是这个模拟用了一个新思路：信息不是非得“一块一块地堆着”，可以“压缩、挤占、重叠”地利用。这个突破，来自 James Cook 和 Ian Mertz 在 2023 年对树评估问题的研究。他们干脆就没遵守“内存空间不能复用”这条祖训，结果真就打开了一个 50 年无人敢碰的口子。

Williams 一开始也不信。他把想法扔在一边两个月，最后实在受不了，找时间自证错误。结果证不出。他一边怀疑人生，一边找人验证，越看越像是真的。

最终的模拟结构暴力地横跨所有算法，通用、彻底、不可否认地表明：小内存，不代表弱计算力。

这个结构还有一个副产物：证明了某些任务，如果不增加空间，时间就无论如何不够用。这在复杂性理论里叫“下界”，也是最难啃的骨头之一。Williams 的方法，像是把所有人都给凶手提供了不在场证明，间接证明了凶手只能是一个。

这结果的规模，可能还无法直接撬开 P vs PSPACE。但他让我们第一次在这个问题上看到“量级上的差异”。未来能不能用多轮迭代，把这个差距放大？没人知道。但这已经是 50 年来的第一次真正突破。

Williams 在本科时就被 Hartmanis 指点过，那位定义了时间复杂度和空间复杂度的祖师爷。但天才也不是一路顺风。Williams 大学申请博士失败，靠 Hartmanis 打电话推荐才混进了硕士项目。第二年才读上 PhD。之后，他用十年时间，做出了计算理论界当年最大的突破，奠定了江湖地位。

而现在，这个突破已经写进了论文，摆在了所有人的桌面上。理论计算机科学界，没有奇迹，只有回头翻笔记。Williams 的突破，不仅说明了“空间真的强于时间”，还让我们看到一种全新的算法变换方式。

如果这条路能继续拓宽，我们或许不止能搞清楚 P 和 PSPACE 的区别，还能打开算法设计、复杂性下界、甚至量子计算的全新路线。

如果你能做出 50 年来最好的结果，那你一定做对了什么。而 Williams 做对的，是一直没有放弃这个“没人看好的”老问题。

有些人，在别人放弃的时候开始思考；在怀疑自己的时候完成证明；在别人都认为没用的地方，挖出金矿。

来源：老胡科学一点号