In Computers, Memory Is More Useful Than Time
19:17 Share

让我们举个例子，假设我把所有的衣服都堆在我的房间角落里。这是最紧凑的储存方式。这堆衣服占用的空间很小，但要找到任何一件衣服都需要很长时间。在这种情况下，找到我最喜欢的毛衣只需要一点空间，却需要很多时间。

但是我厌倦了为了找到想穿的衣服而翻箱倒柜，更不用说衣服上的褶皱了，所以我决定实行一个新的系统。我将把每一件衣服都放进一个标有清晰标签的盒子里，然后按字母顺序排列，堆放在我的房间里。

这样，我就能立即找到那件毛衣，但是现在我的房间里到处都是盒子。同样的过程，找到那件毛衣，现在需要大量的空间，但却可以在很短的时间内完成。我把房间里的一些空间换成了早上更多的空闲时间。如果你能想到更好的方法来整理我的衣服并找到那件毛衣，我很想听听。顺便说一句，你现在有点像计算机科学家了。

欢迎收听Quanta播客，我们将探索基础科学和数学的前沿领域。我是Samir Patel，Quanta杂志的主编，而这个关于衣服的比喻来自于我们Quanta的一位撰稿人Ben Brubaker。Ben去年在我们的名为《Fundamentals》的新闻通讯中写到了计算机科学中时间和空间之间的这种权衡。你绝对应该在quantamagazine.org上注册。

解决我衣服难题最明显的办法是弄一个衣柜来平衡我的空间和时间资源，这很简单。但是要完全掌握计算机科学家如何看待空间和时间，那就复杂一些了。

Ben定期为Quanta撰写关于计算机科学领域发展的文章，他最新的文章追踪了一个与空间和时间相关的重大突破，专家称之为令人震惊、巨大和美丽的突破，我们想谈谈它。所以，Ben，欢迎来到节目。非常感谢你邀请我。

在我们深入探讨之前，最大的想法是什么？我们将要进行什么样的对话？是的，我真的很兴奋这个故事。它讲述的是一位超级研究人员用数学方法证明，空间以一种研究人员完全没有预料到的令人惊讶的方式比时间更强大。

在我们开始讨论空间、时间和所有这些概念之前，你在Quanta的领域是计算机科学，特别是我们所说的理论计算机科学。你能告诉我们那是什么吗？是的。

是的，当大多数人想到计算机科学时，他们会想到编程。而这真的不是我所涵盖的内容。我非常喜欢这位计算机科学先驱Edgar Dijkstra的一句话。他说，计算机科学与计算机的关系就像天文学与望远镜的关系一样。所以，这意味着你实际上要用计算机做事情是次要的。理论计算机科学是一种用数学方法思考算法的方式。现在，这听起来仍然很像计算机，但我更喜欢用更简单的术语来思考它。它是做事的方法。

当你说到“做事”时，在这种情况下，实际“做事”的主要机制是算法，对吧？是的，没错。所以当理论计算机科学家谈到计算时，他们的意思是解决特定问题。就像衣柜的例子一样，你想解决的问题是整理你的衣柜。这是一个计算问题，即使它没有使用计算机。比如规划你的通勤也是一个计算问题。所有这些都是问题，因为你可以考虑用逐步的过程来解决它们。

这就是我们所说的算法。所以不同的算法就像解决这些问题的不同程序。我们有一个问题。如何按字母顺序排列书架上的所有书籍，这是我另一个知道的比喻。而算法就是你取下一本书，看看作者的姓氏是什么，然后取下另一本。如果它

在字母表中位于他名字之前，你把它放在前面；如果你取下另一本，它位于她名字之前，你把它放在另一边。这是一组特定的指令，允许你完成任务或解决问题。没错。所以……

从这里你可以立即看出，有些算法会比其他算法好得多。我可以把所有的书都扔在地上，然后随机地把它们放在书架上，检查一下。这是按字母顺序排列的吗？哦，不是按字母顺序排列的。让我再试一次。这是一个糟糕的算法，会有很多更好的算法。所以计算机科学家经常对什么是最好的算法感兴趣。

我认为，这听起来像是计算机科学的一个基本问题，即我们如何定义一个好的算法？你之前提到了空间和时间的概念。是的。我认为这些是构成算法好坏的基本资源。但在这种情况下，我们所说的空间和时间是什么意思？

时间与我们在日常生活中所说的含义非常相似。如果你要做什么，比如任何一种程序，那都需要一些时间。理想情况下，如果你能做到的话，你希望它花费更少的时间。空间也是类似的。它有点抽象，但你可以把它想象成你房间里的物理空间，或者你可以把它想象成内存。比如，如果你要完成某项任务，你可能需要这样想，“哦，我得到了这个部分结果。我有这个信息，我需要记住它。然后我需要获取一些其他信息。我需要记住它。最终，我将在最后使用所有这些信息。”

例如，如果我正在穿过迷宫，我可能想写下，“这就是这个交叉路口的样子。我以前来过这里。”但是如果我需要经常这样做，那也很笨拙。就像花费很多时间一样。所以空间使用很重要，但你可能也希望最小化它。

从理论上讲，我们正在对它进行抽象，但这几乎就是例如在我们计算机中发生的事情。是的，没错。就像我们知道当我们的计算机变慢时，它需要更多时间来做某事。我们知道，“哦，我们应该看看，哦，我开了数百万个标签。我使用了大量的内存。我正在占用空间来到达那里。”

是的。所以抽象的作用是允许你以更精确的方式提出这些问题。因为如果我想说，“好吧，这个算法使用了大量的空间，这个算法使用了大量的时间，哪个更好？”我将比较一分钟和一兆字节。就像，祝你好运弄清楚那是什么意思。没错。没错。或者即使我只考虑时间，就像

我有一个算法。我在我的电脑上运行它。它非常快。你在你的电脑上运行它，你的电脑很旧。现在它很慢。我不应该把这归咎于算法。但是，我怎么知道该用哪个时间呢？所以用数学术语来定义这些东西是一种摆脱所有不必要细节的方法，只是为了解决问题的核心：算法是什么样的？从更基本的意义上说，它有多快？

这与我认为是计算机科学核心计算问题之一的计算复杂性理论有关。所以现在我们将采取下一步，试图了解新的发现是什么。那么计算复杂性理论是如何融入这一切的呢？

到目前为止，我们讨论的所有内容，你仍然可以在许多不同的层面上提出这些问题。所以你可以说，我将询问关于衣柜整理的特定算法，我将比较所有这些算法，并试图询问这个问题的最佳算法是什么。而且，你知道，它会深入到细节中。计算复杂性就像同一主题的10000英尺高度的视角。所以这就像计算机科学家真的在问关于……

什么是时间？时间有多强大？空间有多强大？证明某事意味着什么？所以他们正在问这些非常崇高的问题，这些问题与这些相同的资源有关，例如关于计算难度和资源的问题，但他们以更放大的方式提出这些问题。所以在计算复杂性理论中，是否存在空间或时间是完成某个任务在

抽象数学空间或现实世界中更有价值的资源的感觉？这是一个很好的问题。让我首先说，你总是需要空间和时间。你永远不会有一个算法只需要零时间。但是你仍然可以问这个问题，比如，空间比时间更强大吗？答案是肯定的。在现实生活中，有一种简单的方法可以考虑这一点。例如，如果

如果我有一个鞋盒，我把鞋子从里面拿出来，我可以把这个盒子用来装其他东西。但是就像2023年一样，我想，“哦，太棒了。我完成了2023年。”就像我完成了我的鞋盒一样。我不能重复使用2023年。它已经过去了。这是对Scott Aronson的转述，他是一位伟大的博主，实际上是Quanta董事会的一位理论计算机科学家。他写了一篇关于这个主题的精彩博客文章。所以在现实生活中，你可以重复使用空间，而你不能重复使用时间。

所以这给了我们一点直觉，也许如果我有一定的空间，我把它与相同的时间量进行比较，同样，我们必须对一定量的空间和时间意味着什么进行非常数学化的处理。但是如果我以正确的方式进行这种苹果与苹果的比较，我认为空间可能会给我带来更多收益。同样，也许我可以少用一些空间，而少量的空间可以给我带来与更多时间相同数量的价值。所以对此有一些直觉。

你使用了这个关键词“直觉”。是的。这是我们认为某些事情是正确的其中一种情况。我们怀疑它是正确的。但是把它变成某种数学真理，就像我们上周谈到的证明一样，这是一个飞跃，需要付出很多努力。所以有一个背景，其中

现在，例如，这个新的发现已经开始以更确定的术语确立空间优先于时间的原则。没错。是的。再次，这与数学研究非常相似，研究人员只有在能够完全严格地证明某些事情时才会感到满意。我之前说过这个结果令人惊讶。但是我说过，你知道，研究人员确实期望空间有时更强大。这并不令人惊讶。它以不同的方式令人惊讶。

所以研究人员认为，如果我有一点空间，那实际上应该帮助我解决许多需要更多时间的问题。这项新的工作表明，那一点空间实际上可以解决所有需要更多时间的问题。所以它在这种全面的广度方面更强大。就像，这真的是关于空间和时间的普遍说法。

在故事中，每个人都应该阅读，我们通过P和P空间的概念得到了这一点。是的。让我们把这提升到另一个抽象层次。那么什么是P，什么是P空间？所以P基本上是一组问题。这就像一组——包括每一个问题，每一个你可以在——我在这里将非常含糊——合理的时间内完成的任务。好的。好的。

P是可以合理时间内解决的问题。而PSPACE，复杂性理论家特别擅长命名。PSPACE对于空间来说是一样的。好的。可以用合理的空间解决的事情。没错。是的。我知道这里有很多复杂性。合理是什么意思？

哦，天哪。是的。这是一个难题。它实际上以一种特定的数学方式定义。但是他们有一个对计算机科学家来说有意义的合理性定义，这使他们能够区分什么是P和什么是P空间。我的意思是，这些都是复杂的定义，但是

研究人员对它们是一致的，并且发现它们对于比较是有用的，对吧？合理只是一个专业术语。没错。所以我们有两组问题，一组可以用合理的时间解决，一组可以用合理的空间解决。这两组问题如何相互作用？

所以复杂性理论家认为P空间比P大得多。更大是指它包含更多问题，更大的一组问题。我们可以用给定数量的空间解决的问题比我们可以用给定数量的时间解决的问题多。没错。这归结于我之前所说的关于重复使用空间的相同直觉。

鞋盒和2023年。所以计算机科学家对“合理”这个词非常慷慨。所以如果你想说，“哦，有一些事情我可以用合理的空间解决，但不能用合理的时间解决”，这仍然包括需要大量时间的问题。所以这个最新的结果是朝着P与C迈出的一步。

P空间问题表明这两个类别并不相同。证明P空间更大。没错。通过以量化的方式证明空间和时间之间较小的差异，它朝着这个方向迈进了一步，如果这说得通的话。空间比时间强大一点。它以这种普遍的方式更强大，就像它对所有问题都更强大一样。但是就它有多强大而言，比如一点空间能为你节省多少额外的时间？

这还不足以让计算机科学家证明P空间大于P。但这被认为是这方面的惊人进步，因为它确实确定了到目前为止一直是直觉的东西。直觉，是的。这是50年来在这方面取得的第一个真正大的进步。所以这是一个巨大的交易。

你提到这背后有一位独特的计算机科学家。是的，没错。所以对我来说，这是一个非常有趣的故事。这位计算机科学家Ryan Williams是该领域的超级明星。他有着取得重大突破的记录。事实证明，他进入计算机科学的经历非常不寻常。而我真正喜欢讲述这个故事的原因是，他……

他在大学里的导师，他生命中这个关键人物在他挣扎时真正指导了他，正是他首先提出了空间和时间的这些定义，他确实是复杂性理论的创始人之一。所以这是一个非常长的故事，从20世纪60年代开始，一直持续到今天。你可以看到这里不同的历史人物在传递火炬。所以可以说空间对于解决问题比时间更重要吗？是的。

是的，我会说时间非常重要，因为你仍然必须花费一些时间。但这告诉你空间非常通用。从某种意义上说，你可以比你想象的更能重复使用空间。例如，你可以在衣柜里装更多东西。我不知道。是的，我想问一下，这如何转化回衣柜的比喻？因为……

这是一种非常直观的方式来思考资源的空间和时间权衡以及解决问题，就像找到我的毛衣一样。是的，没错。对于特定问题，我应该说，我们已经知道很多权衡空间和时间的方法。我的意思是，即使在你的介绍中，你已经有一些很好的例子了。就像，“好吧，我可以这样做，这会使用更多的时间，但空间更少。”是的。

但问题是，这就像真的很奇怪。这就像我想出了这个策略，就像，“哦，你知道，我将使用这个简单的技巧，它将释放我的衣柜中的一点空间并使用更多的时间。”太棒了。我也可以将相同的数学技巧用于规划我的通勤、整理我的书架，或者我能够完成的任何其他任务。同样的事情将节省我相同数量的空间与时间之比。所以这是一种令人难以置信的事情。甚至很难想象这怎么可能。是的，这就是效用——

将这样的东西从例子转化为数学抽象，因为这意味着你可以在数学意义上计算某些东西，并说，“好吧，这应该适用于所有这些问题。”但是我们是否知道这个解决方案是如何朝着实际上可能影响计算机工作方式或解决问题的方式迈进的一步？是的。

是的，所以它不太可能很快有任何实际应用。好的。原因在于计算机科学家对“合理”的定义非常慷慨，正如我所说的那样。所以为了使这些东西在数学上精确，你需要从现实世界中抽象出足够远的东西，然后如果你尝试这样做，你会想，“等等。”

就像，发生了什么？但是，在理论计算机科学和复杂性理论中，这些超级数学结果确实有很多先例，最终转化为真正的进步。例如，密码学中有很多复杂性理论，它可以保护我们互联网上的数据安全。这使用了大量来自复杂性理论的结果。是的，当然。它每天都非常有用。没有它，我们就不会拥有现代生活。

感谢你的加入，Ben。我认为每个人都应该去阅读你的故事，了解更多关于Ryan Williams的故事，并更深入地研究这种复杂性，理想情况下还可以阅读你写的一些与复杂性理论相关的其他Quanta故事。在我让你离开之前，我们很想听听你的推荐。本周有什么东西让你兴奋不已吗？

冒着听起来很自负的风险，最近本周最让我兴奋的是《尤利西斯》，这是詹姆斯·乔伊斯的一部巨型现代主义小说。这是我最喜欢的书之一，我目前正在和Quanta的一些同事以及其他人一起在读书俱乐部里重读它。所以最近关于这方面有一些非常令人振奋的谈话。是的，这真的很有趣。我等不及你们读完这本书，然后我们可以对《尤利西斯》做一个回顾。也许在这里。是的，Quanta播客的特别节目。

好的。谢谢你加入我们，Ben。非常感谢你。本周在quantummagazine.org上，你还可以查看一篇关于费马大定理的数学故事，以及与一位倡导节俭科学或将科学工具掌握在每个人手中的生物工程师的访谈。在我们姐妹播客《The Joy of Why》上，你可以听到与哈佛大学物理学家Kumrun Vafa关于弦理论的对话。

今天，我们将用最早的电子音乐录音来结束节目。它是由BBC于1951年在曼彻斯特的计算机实验室用Mark II机器制作的，该机器是由计算机先驱艾伦·图灵设计的。这段录音于2016年由新西兰的两名科学家修复。这是格伦·米勒的《In the Mood》。

这台机器显然没有心情。

Quanta播客是Quanta杂志的播客，Quanta杂志是一个由西蒙斯基金会支持的编辑独立出版物。我是Quanta的主编Samir Patel。

西蒙斯基金会的资金决定不会影响本播客或Quanta杂志中主题、嘉宾或其他编辑决定的选择。Quanta播客是与PRX Productions合作制作的。制作团队包括Ali Budner、Deborah J. Balthazar、Genevieve Sponsler和Tommy Bazarian。PRX Productions的执行制片人是Jocelyn Gonzalez。

来自Quanta杂志，Simon France和我本人在Matt Karlstrom、Samuel Velasco、Simone Barr和Michael Kanyangolo的支持下提供编辑指导。我们的主题音乐来自APM Music。如果你有任何问题或意见，请发送电子邮件至[email protected]。感谢收听。