摘要：2024年 7 月的下午，瑞恩·威廉姆斯他开始证明自己错了。两个月过去了，他突然发现了计算中时间和记忆之间关系的惊人发现。这是一个数学证明的粗略草图，证明内存比计算机科学家认为的更强大：在所有可以想象的计算中，少量的内存与大量时间一样有用。这听起来太不可能了，

本·布鲁贝克 特约撰稿人

2024年 7 月的下午，瑞恩·威廉姆斯他开始证明自己错了。两个月过去了，他突然发现了计算中时间和记忆之间关系的惊人发现。这是一个数学证明的粗略草图，证明内存比计算机科学家认为的更强大：在所有可以想象的计算中，少量的内存与大量时间一样有用。这听起来太不可能了，以至于他认为一定有什么地方出错了，他立即把证据放在一边，专注于不那么疯狂的想法。现在，他终于抽出时间来找到错误。

事实并非如此。经过数小时仔细研究他的论点，威廉姆斯没有发现任何缺陷。

“我只是觉得我疯了，”麻省理工学院（Massachusetts Institute of Technology）的理论计算机科学家威廉姆斯说。他第一次开始接受这样一种可能性，即也许，只是也许，记忆真的像他的研究所暗示的那样强大。

在接下来的几个月里，他充实了细节，仔细检查了每一步，并征求了其他一些研究人员的反馈。2 月，他终于在网上发布了他的证明（打开新标签页）》中发表的文章获得了广泛好评。

“这太神奇了。太美了，”他说阿维·维格德森（打开新标签页），他是新泽西州普林斯顿高等研究所 （Institute for Advanced Study） 的理论计算机科学家。威格德森一听到这个消息，就给威廉姆斯发了一封祝贺电子邮件。邮件的主题是：“你让我大吃一惊。

时间和内存（也称为空间）是计算中的两个最基本资源：每个算法都需要一些时间来运行，并且在运行时需要一些空间来存储数据。到目前为止，唯一已知的用于完成某些任务的算法需要的空间量与它们的运行时间大致成正比，研究人员长期以来一直认为没有办法做得更好。威廉姆斯的证明建立了一个数学程序，用于将任何算法（无论它做什么）转换为使用更少空间的形式。

Ryan Williams 用一个关于计算中时间和空间之间关系的里程碑式证明震惊了他的同事。

Katherine Taylor 为 Quanta 杂志拍摄

更重要的是，这个结果——关于在一定空间内可以计算什么的陈述——也意味着第二个结果，关于你在一定时间内无法计算什么。第二个结果本身并不令人惊讶：研究人员预计它是真的，但他们不知道如何证明它。Williams 的解决方案基于他全面的第一个结果，感觉几乎卡通化地过度，类似于通过为地球上的其他人建立铁定的不在场证明来证明嫌疑犯有罪。它还可能提供一种新方法来解决计算机科学中最古老的悬而未决的问题之一。

“这是一个非常惊人的结果，也是一个巨大的进步，”他说保罗·比姆（打开新标签页），华盛顿大学的计算机科学家。“这是 Ryan 做的事，这并不令人惊讶。”

46 岁的威廉姆斯有一张开朗、富有表现力的脸，头发上带着一丝灰色。他的办公室可以俯瞰麻省理工学院斯塔塔中心（Stata Center）五颜六色的尖顶，这是创造性利用空间的另一个例证。一对瑜伽垫将窗台变成了一个临时的阅读角，书桌被塞进一个形状奇特的角落里，为沙发腾出空间，面对着一块写满数学涂鸦的大白板。

麻省理工学院与威廉姆斯在阿拉巴马州农村的童年家相距甚远，那里不乏空间。他在一个 50 英亩的农场长大，7 岁时第一次看到电脑，当时他的母亲开车带他穿越县城参加一个特殊的学术充实课程。他回忆说，他被一个生成数字烟花表演的简单程序所震撼。

“它采用随机颜色，并从显示器中间向随机方向发送，”Williams 说。“你无法预测你会得到什么照片。”计算机世界似乎是一个狂野而美妙的游乐场，充满了无限的可能性。年轻的 Williams 被迷住了。

“我在纸上为自己编写程序，以便在未来的计算机上运行，”他说。“我的父母真的不知道该怎么处理我。”

Williams 的办公室和他的新结果一样，创造性地利用了空间。

随着年龄的增长，Williams 从虚构的计算机发展到真实的计算机。在高中的最后两年，他转学到著名的公立寄宿学校阿拉巴马州数学与科学学院，在那里他第一次接触到了计算机科学的理论方面。

“我意识到外面有更广阔的事物世界，而且有一种方法可以用数学方式思考计算机，”他说。“这就是我想做的。”

Williams 特别被理论计算机科学的一个分支所吸引，该分支称为计算复杂性理论。它涉及解决计算问题（例如排序列表或因式分解数字）所需的资源（例如时间和空间）。大多数问题可以通过许多不同的算法来解决，每种算法都有自己的时间和空间要求。复杂性理论家根据用于解决问题的最佳算法的资源需求（即运行速度最快或使用最少空间的算法）将问题分为几类，称为复杂性类。

但是，您如何使计算资源的研究在数学上更加严谨呢？如果您尝试通过将分钟与兆字节进行比较来分析时间和空间，您将不会走得太远。要取得任何进展，您需要从正确的定义开始。

这感觉几乎是卡通化的过度，类似于通过为地球上的其他人建立不在场证明来证明嫌疑凶手有罪。

这些定义来自 Juris Hartmanis 的工作，Juris Hartmanis 是一位开创性的计算机科学家，他有利用有限资源凑合的经验。他于 1928 年出生于一个著名的拉脱维亚家庭，但他的童年被第二次世界大战的爆发打乱了。苏联占领军逮捕并处决了他的父亲，战后，哈特曼尼斯在难民营完成了高中学业。他继续上大学，尽管他买不起教科书，但他还是取得了优异的成绩。

“我通过在讲座中做非常详细的笔记来补偿，”他在2009 年采访（打开新标签页）.“[拥有] 即兴发挥和克服困难有一定的优势。”哈特曼尼斯于 1949 年移民到美国，在堪萨斯城大学学习数学的同时，做过一系列零工——建造农业机械、制造钢铁，甚至担任管家。他在理论计算机科学这一年轻的领域取得了巨大的成功。

1960 年，Hartmanis 在纽约斯克内克塔迪的通用电气研究实验室工作时，遇到了正在进行暑期实习的研究生 Richard Stearns。在一双开创性（打开新标签页） 文件（打开新标签页）他们为时间和空间建立了精确的数学定义。这些定义为研究人员提供了比较这两种资源并将问题分类为复杂度类别所需的语言。

在 1960 年代，Juris Hartmanis 建立了计算机科学家用来分析空间和时间的定义。

康奈尔大学图书馆珍本和手稿馆藏部

最重要的类之一有一个不起眼的名字 “P”。粗略地说，它包含了可以在合理时间内解决的所有问题。一个类似的空间复杂度类被称为 “PSPACE”。

这两类之间的关系是复杂性理论的核心问题之一。P 中的每个问题也都在 PSPACE 中，因为快速算法没有足够的时间来填充计算机内存中的太多空间。如果相反的说法也成立，那么这两个类将是等价的：空间和时间将具有相当的计算能力。但复杂性理论家怀疑 PSPACE 是一个大得多的类，包含许多 P 中没有的问题。换句话说，他们认为空间是比时间强大得多的计算资源。这种信念源于这样一个事实，即算法可以一遍又一遍地使用同一小块内存，而时间并不那么宽容——一旦它过去了，你就无法取回它。

“The intuition is just so simple,” Williams said. “You can reuse space, but you can’t reuse time.”

But intuition isn’t good enough for complexity theorists: They want rigorous proof. To prove that PSPACE is larger than P, researchers would have to show that for some problems in PSPACE, fast algorithms are categorically impossible. Where would they even start?

As it happened, they started at Cornell University, where Hartmanis moved in 1965 to head the newly established computer science department. Under his leadership it quickly became a center of research in complexity theory, and in the early 1970s, a pair of researchers there, John Hopcroft and Wolfgang Paul, set out to establish a precise link between time and space.

I thought about it, and I was like, ‘Well, that just simply can’t be true.’

Ryan Williams

Hopcroft and Paul knew that to resolve the P versus PSPACE problem, they’d have to prove that you can’t do certain computations in a limited amount of time. But it’s hard to prove a negative. Instead, they decided to flip the problem on its head and explore what you can do with limited space. They hoped to prove that algorithms given a certain space budget can solve all the same problems as algorithms with a slightly larger time budget. That would indicate that space is at least slightly more powerful than time — a small but necessary step toward showing that PSPACE is larger than P.

考虑到这个目标，他们转向了一种复杂性理论家称为模拟的方法，该方法涉及将现有算法转换为解决相同问题的新算法，但空间和时间不同。要理解基本概念，假设您有一个快速算法，用于按字母顺序排列书架，但它需要您将书籍排列成数十小堆。您可能更喜欢一种在公寓中占用更少空间的方法，即使它需要更长的时间。模拟是一种数学过程，您可以使用它来获得更合适的算法：将原始算法提供给它，它会为您提供一种以牺牲时间为代价节省空间的新算法。

算法设计人员长期以来一直在研究特定任务（如排序）的这些时空权衡。但是，为了在时间和空间之间建立一般关系，Hopcroft 和 Paul 需要更全面的方法：一种节省空间的仿真程序，该程序适用于每种算法，无论它解决了什么问题。他们预计这种普遍性是有代价的。通用仿真无法利用任何特定问题的细节，因此它可能不会像专用仿真那样节省那么多空间。但是当 Hopcroft 和 Paul 开始他们的工作时，根本没有已知的节省空间的通用方法。即使节省少量也会是一种进步。

1975 年，霍普克罗夫特和保罗与一位名叫莱斯利·瓦利恩特（打开新标签页）。三人组设计了一个通用模拟程序（打开新标签页）这总是可以节省一点空间。无论你给它什么算法，你都会得到一个等效的算法，它的空间预算略小于原始算法的时间预算。

“你能在这么短的时间内做的任何事情，你也可以在稍小的空间里做，”Valiant 说。这是寻求连接空间和时间的第一步。

1975 年，莱斯利·瓦利安特 （Leslie Valiant） 帮助证明了空间是一种比时间更强大的计算资源。

但随后进展停滞不前，复杂性理论家开始怀疑他们遇到了一个根本性的障碍。问题恰恰在于 Hopcroft、Paul 和 Valiant 模拟的通用特性。虽然许多问题可以用比时间小得多的空间来解决，但有些问题在直觉上似乎需要的空间几乎与时间一样多。如果是这样，那么更节省空间的通用模拟就不可能了。Paul 和另外两名研究人员很快证明他们是确实不可能（打开新标签页），前提是您做出一个看似明显的假设：不同的数据块不能同时占用相同的内存空间。

“每个人都理所当然地认为你不能做得更好，”Wigderson 说。

Paul 的结果表明，解决 P 与 PSPACE 问题需要完全放弃仿真，转而采用不同的方法，但没有人有任何好主意。这就是问题存在 50 年的地方——直到 Williams 最终打破了僵局。

首先，他必须读完大学。

1996 年，威廉姆斯申请大学的时候到了。他知道追求复杂性理论会让他远离家乡，但他的父母明确表示，西海岸和加拿大是不可能的。在他剩下的选择中，康奈尔大学在他最喜欢的学科的历史上占有突出的地位。

“这个家伙 Hartmanis 定义了时间和空间复杂度类，”他回忆起当时的想法。“这对我来说很重要。”

威廉姆斯在慷慨的经济援助下被康奈尔大学录取，并于 1997 年秋天来到康奈尔大学，计划不惜一切代价成为一名复杂性理论家。他的一心一意让他的同学们印象深刻。

“他只是复杂性理论的超级骗子，”他说斯科特·阿伦森（打开新标签页），德克萨斯大学奥斯汀分校的计算机科学家，与康奈尔大学的 Williams 重叠。

威廉姆斯在本科时就对空间和时间之间的关系产生了兴趣，但直到去年才找到研究它的机会。

但到了大二，威廉姆斯正在努力跟上强调数学严谨性而不是直觉的课程。他在一门计算机理论课上取得了中等成绩后，老师建议他考虑其他职业。但威廉姆斯不会放弃他的梦想。他加倍努力，报名参加了一门研究生理论课程，希望在较难的课程中取得优异的成绩，在他的研究生院申请中看起来会给人留下深刻印象。教授那门研究生课程的教授是哈特曼尼斯，当时他是该领域的元老级政治家。

Williams 开始每周参加 Hartmanis 的办公时间，在那里他几乎总是唯一出现的学生。他的坚韧得到了回报：他在课程中获得了 A，Hartmanis 同意在下学期为他的独立研究项目提供建议。在 Williams 的大学期间，他们每周的会议仍在继续。Hartmanis 鼓励他培养一种独特的复杂性研究方法，并温柔地引导他远离死胡同。

“那时我深受他的影响，”威廉姆斯说。“我想我现在仍然如此。”

如果你得到任何数学结果是 50 年来最好的事情，那你一定做对了什么。

莱斯利·瓦利恩特

但是，尽管从美国国家科学基金会（National Science Foundation）获得了梦寐以求的研究生研究奖学金，威廉姆斯还是被他申请的每个博士课程都拒绝了。听到这个消息后，哈特曼尼斯打电话给一位同事，然后转身祝贺威廉姆斯被康奈尔大学为期一年的硕士课程录取。一年后，Williams 再次申请了各种博士课程，凭借额外的研究经验，他获得了成功。

Williams 在研究生院和随后的几年里继续研究复杂性理论。2010 年，在获得博士学位四年后，他证明了自己里程碑结果（打开新标签页）— 这是一小步，但却是几十年来最大的一步，朝着解决理论计算机科学中最著名的问题，即困难问题的性质迈出。这一结果巩固了 Williams 的声誉，他继续撰写了数十篇关于复杂性理论不同主题的其他论文。

P 与 PSPACE 不是其中之一。自从他在大学里第一次遇到这个问题以来，他就一直对这个问题着迷。他甚至在他的计算机科学课程中加入了逻辑和哲学课程，从其他时间和空间的角度寻求灵感，但无济于事。

“它一直在我的脑海中，”威廉姆斯说。“我就是想不出什么有趣的东西来说。”

去年，他终于找到了他一直在等待的机会。

Williams 的新结果始于关于计算中内存的不同问题的进展：在极其有限的空间下可以解决哪些问题？2010 年，复杂性理论先驱斯蒂芬·库克 （Stephen Cook） 和他的合作者发明了一项名为树评估问题（打开新标签页），他们证明，对于空间预算低于特定阈值的任何算法来说，这是不可能的。但有一个漏洞。该证明依赖于 Paul 和他的同事几十年前所做的相同常识性假设：算法无法在已经满的空间中存储新数据。

十多年来，复杂性理论家试图堵住这个漏洞。然后，在 2023 年，库克的儿子詹姆斯（打开新标签页）和一位名为伊恩·默茨（打开新标签页）把它吹得大大的，设计算法（打开新标签页）这解决了树评估问题，使用的空间比任何人认为的要小得多。老库克的证明假设数据位就像鹅卵石，必须在算法的内存中占据不同的位置。但事实证明，这并不是存储数据的唯一方式。“我们实际上可以将这些鹅卵石视为我们可以在彼此重叠上稍微挤压的东西，”Beame 说。

詹姆斯·库克（James Cook，左）和伊恩·默茨（Ian Mertz）最近设计了一种新算法，该算法使用的空间比任何人认为的要小得多，从而解决了特定问题。

科林·莫里斯;米哈尔·库基

Cook 和 Mertz 的算法引起了许多研究人员的好奇心，但尚不清楚它是否在树评估问题之外有任何应用。“没有人看到它与时间本身的关系有多重要，”Wigderson 说。

瑞恩·威廉姆斯是个例外。2024 年春天，一群学生在他教授的一门课上做了关于 Cook 和 Mertz 论文的演讲，作为他们的最后一个项目。他们的热情激发了他仔细观察。他一这样做，一个想法就跳了出来。他意识到，Cook 和 Mertz 的方法实际上是减少空间使用的通用工具。为什么不用它来驱动连接时间和空间的新的通用模拟——就像 Hopcroft、Paul 和 Valiant 设计的那个，但更好呢？

这个经典的结果是，将具有给定时间预算的任何算法转换为空间预算略小的新算法。Williams 发现，基于柔软鹅卵石的模拟将使新算法的空间使用量大大减少——大约等于原始算法时间预算的平方根。这种新的节省空间的算法也会慢得多，因此模拟不太可能有实际应用。但从理论的角度来看，这简直是革命性的。

催化计算利用完整硬盘的全部功能

计算复杂性催化计算利用完整硬盘的全部功能

2月 18， 2025

50 年来，研究人员一直认为不可能改进 Hopcroft、Paul 和 Valiant 的通用模拟。Williams 的想法——如果成功的话——不仅会打破他们的记录，还会摧毁它。

“我想了想，我就想，'嗯，这根本不可能是真的，'”威廉姆斯说。他把它放在一边，直到 7 月的那个决定性的日子才回来，当时他试图找到论点中的缺陷，但失败了。在他意识到没有缺陷后，他花了几个月的时间写来写和重写证明，以使其尽可能清晰。

2 月底，威廉姆斯终于将完成的纸张放在网上（打开新标签页）。库克和默茨和其他人一样感到惊讶。“我必须先走很长一段路，然后才能做其他任何事情，”默茨说。

Valiant 在早上通勤时偷偷了解了 Williams 在他几十年前的成绩上的进步。多年来，他一直在哈佛大学任教，就在 Williams 在麻省理工学院的办公室的不远处。他们以前见过面，但他们不知道他们住在同一个社区，直到他们在二月的一个下雪天在公共汽车上撞见对方，就在结果公布的几周前。Williams 向吃惊的 Valiant 描述了他的证据，并承诺会把他的论文寄出去。

“我印象非常非常深刻，”Valiant 说。“如果你得到任何数学结果是 50 年来最好的事情，那你一定做对了。”

通过他的新模拟，Williams 证明了关于空间计算能力的积极结果：使用相对较少空间的算法可以解决所有需要更多时间的问题。然后，他只用了几行数学代码，就把它颠倒过来，证明了关于时间计算能力的负面结果：除非你使用比空间更多的时间，否则至少有几个问题无法解决。第二个范围更窄的结果与研究人员的预期一致。奇怪的是 Williams 是如何做到这一点的，他首先证明了一个适用于所有算法的结果，无论它们解决了什么问题。

“我仍然很难相信，”威廉姆斯说。“这似乎好得令人难以置信。”

威廉姆斯使用库克和默茨的技术在空间和时间之间建立了更牢固的联系——这是 50 年来在这个问题上的首次进展。

用定性术语来说，Williams 的第二个结果听起来像是 P 与 PSPACE 问题的长期寻求的解决方案。区别在于规模问题。P 和 PSPACE 是非常广泛的复杂度类别，而 Williams 的结果则处于更精细的层次。他在空间的力量和时间的力量之间建立了一个定量的差距，为了证明 PSPACE 大于 P，研究人员必须把这个差距做得大大、大得多。

这是一个艰巨的挑战，类似于用撬棍撬开人行道的裂缝，直到它与大峡谷一样宽。但是，通过使用 Williams 模拟程序的修改版本，可以多次重复关键步骤，每次节省一点空间。这就像一种反复增加撬棍长度的方法——让它足够大，你就可以撬开任何东西。这种反复的改进不适用于当前版本的算法，但研究人员不知道这是否是一个根本限制。

“这可能是一个终极瓶颈，也可能是一个 50 年的瓶颈，”Valiant 说。“或者这可能是下周有人可以解决的问题。”

如果下周问题得到解决，威廉姆斯将自责。在他写这篇论文之前，他花了几个月的时间尝试扩展他的结果，但都没有成功。但即使这种延期是不可能的，威廉姆斯也相信，更多的太空探索必然会带来一些有趣的地方——也许会在一个完全不同的问题上取得进展。

“我永远无法准确地证明我想证明的事情，”他说。“但通常情况下，我证明的东西比我想要的要好得多。”

来源：人工智能学家