对于算法而言，一点内存胜过大量时间
一位计算机科学家的“惊人”证明是过去50年来计算机科学领域最著名问题之一取得的首次进展。
2024年7月的一个下午，瑞安·威廉姆斯决定证明自己错了。两个月前，他偶然发现了一个关于计算中时间与内存关系的惊人发现。这是一个粗略的数学证明草稿，表明内存比计算机科学家所相信的更强大：在所有可想象的计算中，少量内存与大量时间同样有用。这听起来如此不可思议，他认为一定有什么地方错了，于是立即搁置了这个证明，转而专注于更不疯狂的想法。如今，他终于抽空寻找其中的错误。
但事实并非如此。经过数小时的仔细推敲，威廉姆斯找不到任何漏洞。
“我以为自己快要疯了，”麻省理工学院的理论计算机科学家威廉姆斯说。他第一次开始考虑，也许，只是也许，记忆真的像他的研究暗示的那样强大。
在接下来的几个月里，他完善了细节，仔细审查了每一步，并征求了其他几位研究人员的反馈。今年2月，他终于将证明发布到网上，获得了广泛赞誉。
“太神奇了。太美妙了，”新泽西州普林斯顿高等研究院的理论计算机科学家阿维·维格德森说道。一听到这个消息，维格德森就给威廉姆斯发了一封祝贺邮件。邮件的主题是：“你让我大开眼界。”
时间和内存(也称为空间)是计算中最基本的两种资源：每个算法都需要一定时间运行，并在运行过程中需要一定空间存储数据。直到现在，已知的所有实现特定任务的算法所需的空间都大致与运行时间成正比，研究人员长期认为无法做得更好。威廉姆斯的证明建立了一种数学方法，可以将任何算法(无论其功能如何)转换为一种使用空间量大大减少的形式。
更重要的是，这一结果——关于在给定空间量下可以计算什么的陈述——也暗示了第二个结果，即在给定时间内无法计算什么。这一第二个结果本身并不令人意外：研究人员一直认为它成立，但他们不知道如何证明它。威廉姆斯的解决方案，基于他开创性的第一个结果，显得几乎夸张到荒谬的地步，就像通过为地球上每个人都建立铁证如山的不在场证明来证明一名涉嫌谋杀者有罪一样。它还可能为解决计算机科学中最古老的开放问题之一提供一种新方法。
“这是一个相当惊人的结果，也是一个巨大的进步，”华盛顿大学的计算机科学家保罗·比姆(Paul Beame)说，“瑞安做到这一点并不令人意外。”
自由的空间
威廉姆斯，46岁，有着一张开朗、富有表现力的脸庞，头发中夹杂着一丝灰白。他的办公室俯瞰着麻省理工学院斯塔塔中心的彩色尖顶，是空间创意利用的又一例证。两块瑜伽垫将窗台改造成了临时阅读角，书桌被安置在一个形状奇特的角落，腾出空间摆放一张面向大型白板的沙发，白板上布满了数学笔记。
麻省理工学院与威廉姆斯在阿拉巴马州农村的童年故居相距甚远，那里从不缺乏空间。他成长于一片50英亩的农场，7岁时第一次见到电脑，当时母亲开车带他跨县参加一门特别的学术提升课程。他回忆起自己被一个简单的数字烟花显示程序深深吸引。
“它会随机选择一种颜色，并从屏幕中央随机方向发射出去，”威廉姆斯说，“你无法预测最终会得到什么画面。” 计算机世界仿佛是一个充满无限可能的奇妙乐园。年轻的威廉姆斯彻底迷上了它。
“我会在纸上写程序，打算在未来的计算机上运行，”他说，“我的父母真的不知道该如何应对我。”
随着年龄增长，威廉姆斯从想象中的计算机过渡到真实的计算机。高中最后两年，他转学至阿拉巴马州数学与科学学校——一所享有盛誉的公立寄宿学校，在那里他首次接触到计算机科学的理论层面。
“我意识到外面还有更广阔的世界，而且可以用数学方法思考计算机，”他说，“这就是我想做的事。”
威廉姆斯特别对理论计算机科学的一个分支——计算复杂性理论——产生了浓厚兴趣。该理论研究解决计算问题(如排序列表或分解数字)所需的资源(如时间和空间)。大多数问题都可以通过多种不同的算法来解决，每种算法对时间和空间都有自己的要求。复杂性理论家根据解决这些问题的最佳算法的资源需求，将问题分类为不同的复杂性类——即运行速度最快或占用空间最少的算法。
但如何使计算资源的研究具有数学上的严谨性？如果你试图通过比较分钟和兆字节来分析时间和空间，你不会走得太远。要取得任何进展，你需要从正确的定义开始。
善用资源
这几乎显得夸张得像卡通一样，就像通过为地球上每个人都证明不在场来证明一名涉嫌谋杀者有罪。
这些定义源自先驱计算机科学家尤里斯·哈特曼尼斯(Juris Hartmanis)的工作，他曾有过在有限资源下工作的经验。他于1928年出生于一个显赫的拉脱维亚家庭，但童年因第二次世界大战爆发而中断。占领的苏联军队逮捕并处决了他的父亲，战争结束后，哈特曼尼斯在难民营完成了高中学业。他随后进入大学深造，尽管无法负担教材费用，但他仍表现优异。
“我通过在课堂上做非常详细的笔记来弥补，”他在2009年的一次采访中回忆道(https://dl.acm.org/doi/10.1145/1141880.1775727)。“在不得不即兴发挥并克服困难的情况下，确实存在某种优势。”哈特曼尼斯于1949年移民至美国，在堪萨斯城大学攻读数学学位期间，他从事过一系列零工——包括制造农业机械、生产钢铁，甚至担任管家。随后，他在新兴的理论计算机科学领域开启了极为成功的职业生涯。
1960年，哈特曼斯在纽约州斯克内克塔迪的通用电气研究实验室工作时，遇到了正在做暑期实习的研究生理查德·斯蒂尔斯。在两篇开创性 论文中，他们为时间和空间建立了精确的数学定义。这些定义为研究人员提供了比较这两种资源并将其分类到复杂性类别的语言。
其中最重要的类之一被称为“P”。大致来说，它涵盖了所有可以在合理时间内解决的问题。与之对应的空间复杂性类被称为“PSPACE”。
这两个类之间的关系是复杂性理论中的核心问题之一。P类中的每个问题也属于PSPACE类，因为快速算法在计算机内存中占用的空间有限。如果反向陈述也成立，则两类问题将等价：空间与时间将具有可比的计算能力。但复杂性理论学家怀疑PSPACE类要大得多，包含许多不属于P类的问题。换言之，他们认为空间作为计算资源远比时间强大。这种信念源于这样一个事实：算法可以反复使用同一小块内存，而时间则没有这么宽容——一旦时间流逝，就无法挽回。
“这种直觉非常简单，”威廉姆斯说，“你可以重复使用空间，但无法重复使用时间。”
但直觉对复杂性理论家来说不够：他们需要严谨的证明。要证明PSPACE大于P，研究人员必须证明对于PSPACE中的某些问题，快速算法在原则上是不可能的。他们该从哪里开始呢？
一场空间之旅
巧合的是，他们从康奈尔大学开始，哈特曼尼斯于1965年搬到那里，担任新成立的计算机科学系主任。在他的领导下，该系迅速成为复杂性理论研究的中心。20世纪70年代初，该系的两位研究人员约翰·霍普克罗夫特和沃尔夫冈·保罗着手建立时间与空间之间的精确联系。
我思考了一下，心想，“这显然不可能是真的。”
瑞安·威廉姆斯
霍普克罗夫特和保罗知道，要解决P与PSPACE问题，他们必须证明某些计算无法在有限时间内完成。但证明否定命题颇具挑战性。于是，他们决定反其道而行之，探索在有限空间内能实现什么。他们希望证明，给定一定空间预算的算法能够解决与时间预算稍大的算法相同的问题。这将表明空间至少在某种程度上比时间更强大——这是证明PSPACE大于P的一个微小但必要的步骤。
怀着这个目标，他们转向了复杂性理论家所称的模拟方法，该方法涉及将现有算法转换为新的算法，这些新算法解决相同的问题，但使用不同的空间和时间。为了理解基本思路，假设你有一个快速的算法可以按字母顺序排列书架上的书籍，但它要求你将书籍分成数十个小堆。你可能更倾向于一种占用公寓空间更少的方法，即使它需要更长时间。模拟是一种数学程序，你可以用它来获得一个更合适的算法：输入原始算法，它会给你一个新的算法，该算法通过牺牲时间来节省空间。
算法设计师长期以来一直研究特定任务(如排序)中的空间-时间权衡。但为了建立时间与空间之间的普遍关系，霍普克罗夫特和保罗需要更全面的方法：一种适用于所有算法的节省空间模拟过程，无论其解决何种问题。他们预计这种普遍性会带来代价。通用模拟无法利用任何特定问题的细节，因此节省的空间可能不如专用模拟多。然而，当霍普克罗夫特和保罗开始研究时，尚无已知的通用节省空间方法。即使节省少量空间也算进步。
突破性进展出现在1975年，当时霍普克罗夫特和保罗与一位名叫莱斯利·瓦利安特的年轻研究员合作。三人组设计了一种通用模拟程序，该程序总能节省一点空间。无论你给它什么算法，你都会得到一个等效的算法，其空间预算比原始算法的时间预算略小。
“只要能在如此多的时间内完成的事情，你也可以在稍小的空间内完成，”瓦利安特说。这是连接空间与时间的首次重大突破。
但随后进展停滞，复杂性理论家开始怀疑他们遇到了根本性障碍。问题恰恰在于霍普克罗夫特、保罗和瓦利安特的模拟具有普适性。虽然许多问题可以用比时间少得多的空间解决，但有些问题直观上似乎需要几乎与时间相当的空间。如果如此，更节省空间的普适性模拟将不可能实现。保罗和其他两位研究人员很快证明，这种模拟确实不可能实现，前提是做出一个看似显而易见的假设：不同的数据块不能在内存中同时占用同一空间。
“大家都认为无法做得更好，”维格德森说。
保罗的结果表明，解决P与PSPACE问题需要完全放弃模拟，转而采用其他方法，但没有人有好的想法。这个问题在50年间一直没有进展——直到威廉姆斯终于打破了僵局。
首先，他必须完成大学学业。
复杂性类
1996年，威廉姆斯到了申请大学的年龄。他知道追求复杂性理论会让他远离家乡，但他的父母明确表示，西海岸和加拿大不在考虑之列。在他剩下的选择中，康奈尔大学因其在自己最喜欢的学科历史上的重要地位而脱颖而出。
“哈特曼斯定义了时间和空间复杂性类，”他回忆道，“这对我很重要。”
威廉姆斯凭借丰厚的经济资助被康奈尔大学录取，并于1997年秋季入学，决心不惜一切代价成为一名复杂性理论家。他的专注态度让同学们印象深刻。
“他就是对复杂性理论超级着迷，”得克萨斯大学奥斯汀分校的计算机科学家斯科特·阿伦森(Scott Aaronson)说，他与威廉姆斯在康奈尔大学有过交集。
但到了大二，威廉姆斯在那些更注重数学严谨性而非直觉的课程中开始感到力不从心。在计算理论课程中获得中等成绩后，老师建议他考虑其他职业方向。但威廉姆斯并未放弃梦想。他加倍努力，报名参加了一门研究生理论课程，希望在更难的课程中取得优异成绩，以提升研究生申请的竞争力。教授这门研究生课程的是哈特曼尼斯，当时他已是该领域的资深专家。
威廉姆斯每周都会参加哈特曼尼斯的办公时间，而他几乎总是唯一一个到场的学生。他的坚持终获回报：他在这门课上获得了A等成绩，哈特曼尼斯也同意在下个学期指导他进行独立研究项目。他们每周的会面一直持续到威廉姆斯大学毕业。哈特曼斯鼓励他培养对复杂性研究的独特视角，并温柔地引导他避开死胡同。
“我当时深受他的影响，”威廉姆斯说，“我想现在仍然如此。”
如果你得到一个在50年内最好的数学结果，那你一定做对了。
莱斯利·瓦利安特
尽管获得了国家科学基金会颁发的珍贵研究生研究奖学金，威廉姆斯申请的每一个博士项目都遭到了拒绝。听到这个消息后，哈特曼斯给一位同事打了电话，然后转身祝贺威廉姆斯被康奈尔大学的一年制硕士项目录取。一年后，威廉姆斯再次申请了多个博士项目，凭借这段额外的研究经验，他最终取得了成功。
威廉姆斯在研究生院及之后的岁月里继续从事复杂性理论研究。2010年，在他获得博士学位四年后，他证明了一个里程碑式结果——这是解决理论计算机科学中最著名的问题关于困难问题本质的最大进展，尽管只是一个小步骤，但却是数十年来最大的突破。这一成果巩固了威廉姆斯的声誉，他随后在复杂性理论的不同领域发表了数十篇论文。
P与PSPACE的问题不在其中。威廉姆斯自大学时代首次接触该问题以来便对其着迷。他甚至通过修读逻辑学和哲学课程来补充计算机科学课程，试图从其他视角对时间和空间的思考中寻找灵感，但未果。
“它一直萦绕在我的脑海中，”威廉姆斯说，“我就是想不出有什么有趣的东西可以关于它说。”
去年，他终于等来了他一直等待的机会。
柔软的鹅卵石
威廉姆斯新结果的故事始于对计算中内存问题的不同进展：哪些问题可以在极度有限的空间内解决？2010年，开创性的复杂性理论家斯蒂芬·库克及其合作者提出了一个名为“树评估问题”(http://arxiv.org/abs/1005.2642)的任务，并证明任何空间预算低于特定阈值的算法都无法解决该问题。但存在一个漏洞。该证明依赖于保罗及其同事数十年前提出的同一常识性假设：算法无法在已满的内存空间中存储新数据。
十多年来，复杂性理论学家一直试图弥补这一漏洞。然后，在2023年，库克的儿子詹姆斯和一名名为伊恩·梅茨的研究人员彻底打破了这一局面，设计出一个算法，该算法使用远少于预期来解决树评估问题，比任何人想象的都要少。老库克的证明假设数据位就像小石子，必须在算法内存中占据独立的位置。但事实证明，这并非存储数据的唯一方式。“我们可以将这些小石子视为可以稍微挤压在一起的东西，”比姆说。
库克和梅茨的算法引起了许多研究者的好奇，但其应用范围似乎仅限于树评估问题。“没有人意识到它在时间与空间关系中的核心地位，”维格德森说。
瑞安·威廉姆斯是个例外。2024年春季，他所教授的一门课程中，一群学生以库克和梅茨的论文为题进行了毕业设计展示。他们的热情激发了他深入研究的兴趣。一旦他开始研究，一个想法立刻跃入脑海。他意识到，库克和梅茨的方法实际上是一种通用工具，用于减少空间使用。为何不利用它来驱动一个新的普适模拟，将时间与空间相连——就像霍普克罗夫特、保罗和瓦利安特设计的那个，但更好？
那个经典结果是一种将任何具有给定时间预算的算法转换为具有稍小空间预算的新算法的方法。威廉姆斯发现，基于柔软石子的模拟可以使新算法的空间使用量大幅减少——大致等于原始算法时间预算的平方根。这种新的空间高效算法也会慢得多，因此模拟可能没有实际应用价值。但从理论角度来看，它堪称革命性。
50年来，研究人员一直认为无法改进霍普克罗夫特、保罗和瓦利安特的通用模拟。威廉姆斯的构想——如果可行——不仅会打破他们的纪录，更会彻底颠覆它。
“我思考了一下，心想，‘这简直不可能是真的，’”威廉姆斯说。他暂时搁置了这个想法，直到7月那个命运多舛的日子，他试图找出论证中的漏洞但未能成功。意识到没有漏洞后，他花了数月时间反复撰写证明，力求使其尽可能清晰。
二月底，威廉姆斯终于将完成的论文发布到网上。库克和梅茨和其他人一样感到惊讶。“我不得不先去散个长长的步，然后才做其他事情，”梅茨说。
瓦利安特在早晨通勤途中提前看到了威廉姆斯对他的数十年旧成果的改进。多年来，他一直在哈佛大学任教，而威廉姆斯的办公室就在麻省理工学院附近。他们之前见过面，但直到在二月的一个下雪天在公交车上偶遇，他们才意识到自己住在同一个社区，而这距离结果公开仅有几周时间。威廉姆斯向惊愕的瓦利安特解释了他的证明，并承诺会寄给他论文。
“我非常、非常钦佩，”瓦利安特说，“如果你得到一个在50年内最好的数学结果，那你一定做对了什么。”
PSPACE：最后的边疆
凭借新的模拟，威廉姆斯证明了关于空间计算能力的积极结果：使用相对较少空间的算法可以解决所有需要稍多时间的问题。随后，他仅用几行数学公式就反转了这一结论，证明了关于时间计算能力的消极结果：至少有几个问题无法解决，除非使用比空间更多的時間。这一更狭窄的结论与研究人员的预期一致。奇怪的是威廉姆斯的证明过程：他首先证明了一个适用于所有算法的结论，无论这些算法解决何种问题。
“我仍然难以置信，”威廉姆斯说，“这似乎好得令人难以置信。”
从定性角度表述，威廉姆斯的第二个结果听起来像是长期以来寻求的P与PSPACE问题解决方案。区别在于规模。P和PSPACE是极为广泛的复杂性类，而威廉姆斯的结果作用于更精细的层面。他确立了空间与时间计算能力之间的定量差距，要证明PSPACE大于P，研究人员必须将这一差距扩大到极大程度。
这是一个令人望而生畏的挑战，就像用撬棍撬开人行道上的裂缝，直到它宽如大峡谷。但可能通过使用威廉姆斯模拟程序的修改版来实现，该程序重复关键步骤多次，每次节省一点空间。这就像一种反复加长撬棍的方法——只要撬棍足够长，就能撬开任何东西。这种重复改进在当前算法版本中行不通，但研究人员尚不清楚这是否是根本性限制。
“这可能是最终瓶颈，也可能是50年瓶颈，”瓦利安特说，“也可能是有人下周就能解决的问题。”
如果问题下周就被解决，威廉姆斯会后悔莫及。在撰写论文之前，他花了数月时间试图扩展他的结果，但未能成功。但即使这种扩展不可能实现，威廉姆斯仍坚信，更多的空间探索必然会带来有趣的成果——或许是在完全不同的问题上取得进展。
“我永远无法精确证明我想要证明的事情，”他说，“但往往，我证明的事情比我想要的要好得多。”
本文文字及图片出自 For Algorithms, a Little Memory Outweighs a Lot of Time
去除冗余：一台在时间_t_内运行的多磁带图灵机可以使用_O(sqrt(t log t))_的空间进行模拟（通常需要超过_t_的时间）。
[https://arxiv.org/abs/2502.17779](https://arxiv.org/abs/2502.17779)
应该先看看评论！
摘自《骆驼书》（我最喜欢的编程书籍之一，不是因为它启发性强，而是因为它有趣）；关于 Perl 哲学：
“如果你内存不足，可以购买更多内存。但如果你时间不足，那就完蛋了。”
这可以双向作用。如果程序需要的内存超过了计算机的容量，它就无法运行，直到你购买更多内存。但如果它需要两倍的时间，至少它还能运行。
现代计算机拥有如此多的内存，以至于感觉它并不重要。将内存用于算法中的数组或垃圾收集器等功能是有意义的。而额外的内存是无用的。你希望所有程序的总和都能用尽所有内存。另一方面，处理器可以进行上下文切换，并尽其所能确保自己保持忙碌。
CPU就像发动机，内存就是油箱。让发动机空转是不好的，但油箱里留着油不会造成伤害，但也不会带来帮助。我不会因为油箱满载而更快到达目的地。
只有在一次运行一个如此耗费内存的程序时才适用，而这种情况通常无法实现。多任务工作负载更为常见，而尽可能多地使用内存的策略在这种环境下无法奏效。
《骆驼书》撰写时，摩尔定律正蓬勃发展。如今你无法再通过增加硬件获得更多时间，但过去这曾行之有效。现在是水平扩展的时代。这依然意味着更多时间。
大脑 大脑 大脑
预先计算的查找表才是王道！
事实上，如果我们能将处理器中所有操作的计算结果集中存储，可能就不再需要处理器了。
快速检索则是另一个线程需要解决的问题。
这让我想起年轻时开始研究存储系统时，曾提议预先计算每个4KB块一次，然后在写入数据时仅使用指向正确块的指针，直到有人指出，唯一4KB块的数量（2^32768）远超宇宙中的原子数量。
看来你其实离实现这个方案并不远，你只需要一个4KB的指针来指向正确的块。事实上，这就是所有存储系统所做的！
这让我想起我曾设想过，将每张小图片都简单地用256种灰度来表示每个像素x（640 x 480 = 307200像素）= 7800万种可能的图片。
实际上，我对为什么这样做是错误的没有直观的理解，除了如果我们将行连接成一个长行，那么图片可以被视为一个307200位长的二进制数，然后我看到它可以表示256^307200种不同的值。这数量庞大：[https://www.wolframalpha.com/input?i=256%5E307200](https://www.wolframalpha.com/input?i=256%5E307200)
7800万是256张不同图片中每张图片307200个像素的总数。你只计算每个像素在每个可能值中的出现次数，但实际上需要计算每个可能值在每个像素上的出现次数，且需乘以所有其他像素的可能组合次数。
可能的图片数量确实是256^307200，这是一个远超7800万的难以想象的大数。（第一个像素的256种可能值 × 第二个像素的256种可能值 × 256种可能值…）
我90年代初也有过类似的想法，并编写了一个程序以较低分辨率遍历所有可能的图像。我离开学校时让程序运行，数小时后回家发现它几乎还没完成第一行像素的处理！这让我深刻意识到数字图像所处的可能性空间究竟有多庞大！
我十几岁刚接触编程时也有过同样的想法。不知道有多少年轻程序员曾有过完全相同的思考过程？
我觉得你应该早就意识到，显然存在超过7800万种可能的640×480灰度图像。有很多直观的例子，但只需想想这个：
[https://images.lsnglobal.com/ZFSJiK61WTql9okXV1N5XyGtCEc=/fi…](https://images.lsnglobal.com/ ZFSJiK61WTql9okXV1N5XyGtCEc=/fit-in/1200×627/filters:quality(80):strip_exif():strip_icc()/200811/16/section_thumb/Tino_Schneider_greyscale_72_cropped3.jpg)
如果只有7800万张可能的照片，那张肖像怎么能如此明显地识别出特定的人？这难道不意味着你的整个图片空间甚至无法容纳德国每个人的一张肖像吗？
“在某个时刻”我确实意识到了这一点。但我缺乏的是对为什么一个数字可以是三位数000到999，每个位置有十种选择，但总数并不是10乘以3种可能的直观理解。我曾尝试让ChatGPT给我一个直观的解释，但它只是陷入了对组合的解释。我知道这是10×10×10，即10³，我不需要再听这个解释，我想要的是为什么不是10×3的直观理解。
> “如果只有7800万种可能的图片，那么这幅肖像怎么能如此明显地代表某一个人？这难道不意味着整个图片空间甚至无法容纳德国每个人的一张肖像吗？”
“一张640×480的计算机图片必须能够容纳德国每个人的一张肖像”这一说法并不直观； 人类无法检查它，人类无法记住7800万张不同的图片，逐一查看它们，并确认它们都足够独特，且在任何情况下都不会用一张图片代表5万人；人类的注意力和记忆力不足以完成这项任务。
尝试从2×2开始，然后是3×3，依此类推，并手动列出所有可能性。
这关注的是错误的重点；如我所说，“我知道它是10×10×10，即10³，我不需要这个解释[关于正确组合], 我想了解的是为什么它_不是_10×3”。
如果使用关键词，ChatGPT可能能够解释组合数学。
我喜欢排列与置换的关系，其中包含一个e的因子。
我有一个朋友有同样的想法，用只有两种颜色的像素字体和16×16画布来实现。结果仍然是2^256。看着这个程序运行并试图估算它何时完成，让我明白了加密的原理。
另一个问题是（如果我们字面理解这个荒谬的提议，即提前计算“所有可能的块”），这样做实际上并没有节省空间，因为你的“指针”与它们指向的块大小相同。
如果你不实际计算每一个区块，那么你就可以使用哈夫曼编码[1]。
我猜想，如果你对即将到来的数据有很好的了解，你可以使用类似的编码方案，其中7位用于指向一个~512位的数据块，而第8位表示接下来的512位无法压缩。
[1]: [https://en.wikipedia.org/wiki/Huffman编码](https://en.wikipedia.org/wiki/Huffman_coding)
在某些情况下，字典编码（你提到的方案大致如此）实际上效果很好。例如常见值或空值（这是常见值的一种常见类型）。只是尝试对每个块都这样做效率较低。你必须让它“值得”，这取决于该值的出现频率。较短的值会导致压缩比变差，但另一方面，这类值在数据中出现的概率往往更高，因此在一定程度上可以弥补这一缺点。
还有其他类似的轻量级编码方案，如RLE、delta和参考帧编码，它们都适用于不同的数据分布。
这个想法并不遥远。你可以对现有数据块计算一个哈希值。存储哈希值与数据块的映射关系。现在，你可以在任何包含该数据块的位置使用该哈希值，即任何重复的数据块都可以使用相同的哈希值。这就是存储去重的工作原理。
不过，存在碰撞的问题……
这可能非常天真，但是否可以将可逆的时间组件融入区分两个哈希计算中？即在解包/外推时它是唯一标识符，但在分解时可折叠回标准计算——这是否可行？
部分哈希确实包含验证位，不仅用于验证哈希完整性，还用于区分两个“相同”的哈希。然而，这类哈希算法通常速度较慢。
你有具体示例吗？这听起来只是哈希值多出几个位。
主要使用GCM（Galois/Counter Mode）。通常对密钥进行标记，但也可对值进行标记以验证碰撞。
但如我所说，速度较慢。
哈希值的定义就是不可逆的。你可以将时间戳与哈希值一起存储，或者在摘要内容中包含时间戳，但时间戳不能是哈希值的一部分。
_> 哈希函数的定义决定了其不可逆性。_
当然可以。你可以生成所有可能的输入，计算哈希值并与给定的哈希值进行比较。
好吧，这可能需要无限的计算资源（时间/能量）。但这只是技术细节，对吧？
_当然可以。你可以生成所有可能的输入_
这完全取决于你对“可逆”的定义。对于每个哈希值，都有无限多个输入可以产生该值。因此，虽然确实可以找到某个输入，使其哈希值为给定值，但你无法知道我最初哈希得到的那个值的具体输入是什么。
哦，当然，时间戳也可以是元数据！
可以使用加密哈希。
这如何绕过鸽巢原理？
我认为在清除数据前必须先比较数据值，只有当块内容完全相同才能进行去重（清除），否则必须保留该块（无法用哈希值替换，因为池中的哈希链接指向不同数据）
哈希碰撞的概率极低。
对于小数据量确实可行。但随着数据量增长，碰撞概率会以非线性速度增加。因此在存储系统（如S3等）中，除非客户接受碰撞风险，否则这种方案不可行。例如存储媒体数据（电影、照片）时可能可行，但不适用于通用数据。
密码学哈希碰撞的概率极低，低到几乎可以忽略不计。其概率甚至比AWS发生火灾且所有备份丢失导致数据丢失的概率还要低。
你说的有道理。
当使用MD5（128位）时，如果AWS S3采用这种技术，只会产生少量碰撞。使用256位则会将碰撞概率降至极低水平，几乎不可能发生。
如果一个4KB块的平均重复概率至少为6.25%（不考虑数据结构等开销），那么这样做是值得的。
另一个问题是，要地址所有可能的4098字节块，你需要一个4098字节的地址。我猜实际计算和重用的块数量会是一个稀疏子集。
或者，你考虑过8字节块吗？
如果块指针是8字节地址，你无需依赖块的稀疏性，事实上，你甚至无需实际拥有这些块。
一种实现自读写、支持空分配和删除的指针类型，在任何良好的类型系统中都可极高效地实现。这简直是零成本抽象的典范！
（说句认真的，如果内存堆和CPU合作，将顶位设置为1的指针解释为63位线性访问/写入的自存储“指针”，这是一个有趣的想法。
如果某些块高度重复，这可能有意义。
这基本上就是ZFS中去重的工作原理。因此，它只有在存储大量重复数据时才有意义，例如虚拟机镜像。
我们知道，当禁用处理器的缓存时，其性能会急剧下降，因此问题在于有多少计算是全新的计算（从未见过）？
虽然这是事实，但有一个小技术细节需要指出：缓存中还包含之前加载并重复使用的数据，而不仅仅是由于之前的计算结果（例如，可执行程序本身或正在处理的文件就是例子）
你可能会对PIFs感兴趣
[https://github.com/philipl/pifs](https://github.com/philipl/pifs)
你说的没错
使用大语言模型（LLM）和缓存（例如常见问题解答）可以节省大量代币积分
人工智能基本上是在解决搜索问题，而模型只是对数据的近似值——就像线性回归或傅立叶变换一样。
训练基本上就是你的预计算。关键是它预计算了一个拥有数十亿个参数的模型，而不是用一组精确的随机答案进行过拟合，呵呵。
_> 使用大语言模型（LLM）和缓存（例如常见问题解答）可以节省大量代币积分_
大语言模型（LLM）提供商是否在不改变向客户计费的代币数量的情况下，对常见问题解答使用缓存？
不，为什么他们要这样做。你应该维护那个缓存。
我真正想知道的是关于缓存提示的大型前缀。他们是否允许你以某种方式管理这一点？关于 llama 和 deepseek 呢？
哦，那不是问题。只需缓存检索查询即可。
都是指针到底
我总是说，再加一层间接引用就行了。
但说真的……解决方案通常是缓存/分片到中间点——例如大语言模型(LLM)的权重——然后存储起来，这样就可以得到一个接近实际问题空间的近似值了！这基本上是许多人工智能算法的做法，包括 MCTS 和大语言模型(LLMs) 等。
> 如果我们将所有操作集中存储
社区级缓存？这基本上就是预编译软件发行版的核心。针对编程语言设计中的障碍“这将是一个不错的功能，但目前尚不清楚如何高效编译它，因此无法实现”，一个解决方案是采用高度并行的云编译技术，配合社区级别的编译器缓存。如果某项功能只需在每次发布时运行一次，那么即使它需要一天时间来解决，你可能也不会介意。
社区级缓存，听起来像是一个实体图书馆（砖瓦结构的那种）
[https://conwaylife.com/wiki/HashLife](https://conwaylife.com/wiki/HashLife) 是一种在康威的生命游戏中实现此功能的算法，而生命游戏是图灵完备的。我记得我第一次看到时完全困惑：这是一个每帧模拟，复杂到无法用公式概括，而你告诉我我可以直接跳到它的未来？
如果我理解正确，它对之间有空白的区域做这件事？
有道理。假设你有一个被空闲区域包围的模式，它会“闪烁”：A-B-A-B-A… 等等。只要没有其他模式侵入，第n代的模式与第n+1000,000代的模式相同。类似地，对于进行3周期、4周期等循环的模式也是如此。
你只需要两点：a) 检测重复模式的方法，以及 b) 区域/模式之间的碰撞检测（在《生命游戏》中有一种叫“光速”的东西，可以帮助实现这一点）。
我并不完全理解这个算法，但据我所知，它比这要通用得多。在每个时间步长中，一个单元的状态仅由其直接邻居决定，这意味着模拟的“光速”为1单元/秒：要预测N个时间步长后的未来，你只需考虑当前计算区域内N个单元范围内的单元，无论该区域外的情况如何。例如，如果你想跳过一个10×10的区域，查看100步后的未来，你需要考虑一个以该10×10区域为中心的210×210区域，计算一次，然后在未来使用该210×210区域作为查找键，获取10×10区域100步后的状态。我认为HashLife也在同时在多个尺度上做类似的事情，还有一些其他技巧。
> 事实上，如果我们把所有在处理器中执行的操作都集中存储起来，我认为我们可能不再需要处理器了。
正在实现你的搜索历史缓存。
我认为空间胜过时间是非常直观的。
在时间复杂度为 O(n) 的情况下，你可以使用 O(n) 个单元格在磁带上，但对于一个长度为 n 的磁带（假设字母表有 2 个符号），可能的符号配置有 O(2^n) 种，因此你可以用 n 个空间做的事情比用 n 个时间做的事情多得多。
我的直觉是：一个单元的值可以代表多个（许多）时间单位用于计算某物的结果。如果你无法存储足够的中间结果，你可能需要反复重新计算相同/相似的结果——至少在某些算法中是这样。因此，一个单元可以代表数百个时间单位的结果，而能够存储/加载该值以供以后重复使用，就可以替代那些相同的数百个时间单位。实际上，空间可以用于“时间压缩”（类似于压缩文件），当时间用于多次计算相似值时。
如果中间结果完全不相关，且工作内容毫无重叠，那么这种情况不成立——空间无法帮助你。编辑：这种问题非常罕见。想象一个命中率为0%的缓存——几乎从未发生过。
而且你不能反过来做（至少在当前的计算术语/概念中）：你不能用单个时间单位作为数百个单元的替代品/代理，因为我们还没有无限宽的SIMD架构。
许多算法都存在空间与时间的权衡。但最佳方案取决于重新计算某项内容的时间/能量成本，与缓存结果的存储/带宽成本之间的对比。
计算成本高、存储成本低 → 缓存结果有助于优化。
带宽有限/存储昂贵，计算简单（例如：当今超快CPU+L1缓存组合）→ 根据需要实时重新计算某些内容更有效。
我怀疑现有软件（组件）中存在大量沿着“节省CPU周期，消耗存储空间”路径设计的方案，而在现代现实中，“节省存储空间，CPU周期成本低廉”的策略会更有效。过去几十年间，CPU速度的提升远超主内存带宽（甚至容量？）。
对于数据中心、超级计算机、嵌入式系统、个人电脑或终端用户的手机，衡量标准可能不同。但基本原理相同。
据我所知，这是动态规划算法的核心洞见；其核心思想是通过 memoization 技术利用递归任务中的冗余性，预先计算较低阶阶段的部分结果。
我认为这个定理对现代大型语言模型（LLMs）非常适用：预先计算权重的大型语言模型可以用于计算非常复杂的算法，这些算法能够近似人类知识，否则这些算法要么无法实现，要么需要多出几个数量级的计算资源来完成。
此外，O(1) 随机内存访问假设使得人们容易忽视内存资源。实际上，当计算机规模与问题规模成比例时，内存访问复杂度更接近 O(n^(1/3))，这一现象在数据中心中已有实际观察。
我忘了 O(1) 访问模型的具体名称。不是 UMA，而是其他模型。
实际上是O(n^(1/2))，因为数据中心是二维的，而非三维的。
（撇开“我们在地球表面建造”的实际考虑不谈，散热限制也迫使你在三维空间中只能构建二维电路。）
更根本的是O(n^(1/2))，因为全息原理指出，给定空间区域中可编码的信息量与该区域的表面积成正比，而非体积。
（更不用说你实际的散热限制了）
只需确保所有计算都在一个具有无限表面积和零体积的体积内进行。编码问题解决。那么，我们能在时空几何中变得多么双曲，而不会让事情变得太奇怪？
嗯，我接受这个观点
如果有一排排的机器机架，那不是三维空间吗？一台机器可以位于另一台机器的上方、后方或侧面，并与之直接连接。而内部组件具有自己的非均匀内存访问。
或者如果你说热量散发与表面积成正比且是二维的，我不知道。我认为水冷系统更注重体积，但我对此不是专家。
那个例子在极限计算中仍然是二维的，因为你可以继续向外扩展（添加建筑物），但不能向上扩展（添加楼层）
你可以增加楼层。有些数据中心有8层，并且有跨楼层的网络架构。
当你达到，比如，100000层时，你无法再增加楼层。此时你的计算机成本将超过地球一个世纪的GDP，因此讨论理论上的扩展定律是没有意义的。最终你会耗尽太阳的能量输出，于是建造一个戴森球，并最终利用所有这些能量。
哦对，所以高度基本上是个常数。肯定是平方根。
所有算法在此情况下均为O(1)
你需要确定哪些参数是常量，哪些是变量。如果将超级计算机的规模调整以适应特定问题，高度会迅速达到上限并可视为常量，而其他维度则为变量。
空间位置与连接拓扑结构几乎无关（好吧，有一点关联）。
另一方面，实际计算机在扩展硬件时可以并行工作，这是图灵机形式化无法涵盖的。哪些算法在受数据局部性限制的情况下能很好地利用大量计算资源，这可能很有趣。（大脑就是这种情况的经典例子。）
多带式TM已经得到了相当充分的研究
直观上是这样，但由于P≠PSPACE尚未被证明，因此显然难以证明。
我认为，由于许多人直觉上认为P ≠ NP，且PSPACE位于多项式层次结构的顶端，因此即使未被证明，它也具有直观性。
甚至没有证明P ≠ EXPTIME哈哈
EDIT：我记错了。
我认为是有的吧？虽然时间久远，但我似乎记得这是从时间层次定理推导出来的。
我以为有某种简单的证明，但目前只能想到时间层次定理。
这篇文章讨论的是一个新证明，其中P == PSPACE。
这是我们直觉上都期待的结果，但有人终于找到了一个晦涩的证明方法。
——–
这是一篇绕来绕去的文章，以迂回的方式揭示了复杂性理论领域的一个重磅炸弹。抱歉剧透了，但嗯，你可能会期待一篇关于P == PSPACE的文章能更快切入正题……
这篇文章并非关于证明P = PSPACE。那将是一个更大的新闻，因为它还直接暗示了P = NP。
我认为这真的取决于具体任务，并不那么直观。在某些情况下，访问内存可能比重复计算更慢，尤其当存储速度较慢时。
一方面是的，另一方面可能存在一些本质上难以并行化的问题（交替机器的PTIME与确定性PSPACE相同），此时空间开销并不能带来显著提升。从t/log t到sqrt(t log t)的性能提升非常巨大，但这并不意味着无限并行化就能带来更多收益。
但你也要花时间更新单元，所以这并不那么直观。
我不确定你在这里的意思。如果你在谈论“更多空间”，那么你可能没有考虑到时间成本。
更准确地说，我认为直观上，可以在给定O(n)空间内解决的任务类比，远大于可以在给定O(n)时间内解决的任务类比。
如果你的程序在 O(n) 时间内运行，它不能使用超过 O(n) 的内存（内存使用量的上界）。
如果你的程序使用 O(n) 的内存，它必须至少在 O(n) 时间内运行（时间的下界）。
这很容易反驳：
> 如果你的程序在 O(n) 时间内运行，它不能使用超过 O(n) 的内存（内存使用量的上界。[sic]
这显然被当今运行的所有软件所反驳。程序（尤其是游戏）显然使用的内存比程序中的指令更多。
> 如果你的程序使用 O(n) 的内存，它必须至少在 O(n) 时间内运行（时间的下界）。
内存炸弹会以惊人的速度消耗惊人的内存量。
>程序（尤其是游戏）显然使用的内存量远超程序中的指令数量。
如何在不向CPU发出指令的情况下访问内存？此外，“显然”并非论据。
>内存炸弹会以惊人的速度消耗大量内存。
如何在不向CPU发出指令的情况下访问内存？此外，“惊人的速度”并非论据。而且，O(n) 本身就是惊人的速度。
> 此外，“显然”并非论据。
正如你的主张显然是错误的。你需要提供证据来证明这一点；尤其是因为存在可以加载多个内存位的指令。
> 如何在不向CPU发出指令的情况下访问内存？
让我反问你：正在运行的指令存在于哪里？没错：在内存中。然而，指令存在于内存中并不意味着它们被访问。指令数量与访问/使用的内存量之间没有直接关系。
这是关于时间和内存复杂度的讨论，属于计算机科学中的正式领域。你的回复反映了你对计算的模糊理解，而这并非此处的讨论重点。
是的，但你断言这种关系是直接相关的——这显然是不正确的。你说它是O(n)内存和O(n)时间，都使用n。这意味着包含x字节的程序只能运行x秒。这显然是不正确的。
>这意味着包含x字节的程序只能运行x秒。
这不是它的意思。如果你不熟悉这种记号，你只是在将自己对计算的个人想法强加到一些符号上。
嗯。告诉我我“愚蠢”并不能让你正确。
换句话说，M ≤ T。
一个时间有界的图灵机也是空间有界的，因为你需要时间来写入那么多单元。但反之则不成立。
这是显而易见的真理。一个在O(n)时间内运行的图灵机必须停止。而在O(n)空间内运行的图灵机则不必停止。
Almondsetat 的证明似乎更显而易见。在 O(n) 时间内，你只能使用 O(n) 空间，因此你是在比较“O(n) 空间，任意时间”与“O(n) 空间，O(n) 时间”，结果发现第一种方式能获得更多资源。
有趣。这是我一直“理所当然”认为的事情，从未深入思考过。
在我职业生涯中，我做过大量光栅图形编程，而图形工作会大量使用查找表。
昨天，我发布了一个我编写的相当简单的工具[0]：一个服务器，它将一组多边形预先加载到数据库中，然后在查询时使用它们。它运行得相当快（但肯定还能更快）。我只花了几个小时就写好了，而且一开始就取得了不错的性能。
这只是些基础内容。我怀疑这种模式并不独特，但这是我多年来一直使用的做法。我尽量在前期完成尽可能多的工作，并将“半成品”结果存储在内存中。
就像我说的，我一直“就是这么做的”，从未真正思考过。我的工作中充满了“经验法则”之类的东西。没有麻省理工学院的教授来教我，但看到这并非只是“老生常谈”确实令人欣慰。
我们每天做的事情中，有很多是我们根本没有意识到的。其中一些无疑源自像他这样聪明的人，他们找到了最佳解决方案（比如服务器[1]中的“绕线数”算法），而另一些则可能来自“脑子不太灵光的程序员”，他们只是在做有意义的事情。
[0] [https://news.ycombinator.com/item?id=44046227](https://news.ycombinator.com/item?id=44046227)
[1] [https://github.com/LittleGreenViper/LGV_TZ_Lookup/blob/e247f…] (https://github.com/LittleGreenViper/LGV_TZ_Lookup/blob/e247f2f97fb83e5392d31f81c321814baa26dc1b/src/Sources/LGV_TZ_Lookup_Query.class.php#L101)
我目前正深入优化一款游戏，有趣的是，我当前取得的优化成果似乎都与查找表概念的扩展以及使用合适的工具密切相关。
我的意思是，传统上人们对查找表的理解往往是编译时静态生成的数组，甚至在运行时初始化时就固定下来，且永不改变。但如果你稍微放松对这个最后一个概念的坚持，允许查找表随时间略微变化，你就可以用相对较少的内存空间获得巨大的性能提升，而不是每帧都浪费周期。
至于合适的工具，我多年来阅读了大量开发日志和研究论文，探讨将工作负载转移到GPU上，但最近几个月对我的游戏进行彻底重构的经历，真的让我豁然开朗。这不仅仅是编译时或运行时早期构建的查找表，而是随时间略微修改的查找表，将其作为纹理发送至GPU并在那里使用。
沿着这个思路继续下去，现在我们只是将内存读写操作称为“查找表”，尽管它们已不再是严格意义上的查找表，但谁又能说清界限究竟在哪里？
在某种程度上，计算机进行的任何严肃工作都必须是那种可以至少部分通过查找表解决的重复性任务。
以游戏为例，绘制精灵图。绘制一个预加载的合理大小的精灵图总是成本很低，因此帧率较低时必须有过多的精灵图。然而，构建一个包含大量真正独特精灵图的实际场景非常困难。一个关卡拥有有限的贴图色板、有限的角色阵容、技能等元素。从物流角度而言，将所有元素同时放入一个场景中已属不易，即便如此数量也不会多到令人发指。因此，唯一导致精灵绘制变慢的场景就是反复绘制同一小部分精灵。相比之下这种情况极为常见：例如持续发射一个持久性弹幕、通过摇杆操作生成尘埃粒子等。
为了避免过多细节（因为我曾共事的人非常多疑，我不想让他们紧张），我们有时会在迭代器内部动态构建查找表。
例如，每个像素块可能有一些通过哈希映射到查找表（LUT）的计算特性，但这些特性会随着图像处理进程而变化。
我们会进行一次“初步处理”运行，先构建查找表，然后进行一次“详细处理”运行，将查找表应用到像素上。
这可能会变得相当复杂。
Ryan Williams 讲座（他如何开始）：[https://www.youtube.com/live/0DrFB2Cp7tg](https://www.youtube.com/live/0DrFB2Cp7tg)
以及论文：[https://people.csail.mit.edu/rrw/time-vs-space.pdf](https://people.csail.mit.edu/rrw/time-vs-space.pdf)
我感到困惑。如果一台单带图灵机接收一个二进制数字N，并需要在数字N的右侧写入N个1，它会执行N步操作。
如果期望输出是N个1，那么这台机器如何能在小于N的空间内被模拟？
这台机器必须在磁带开头减去数字N，然后移动到磁带末尾写入“1”，因此它运行时间为O(N^2)，而不是O(N)？（因为它需要N次“往返”到磁带末尾，每次“往返”需要1、2、3…N步）
由于图灵机无法在常数时间内跳转到磁带上的任意位置（就像计算机可以做到的那样），这是否会对实际计算机产生影响？
多磁带图灵机在运行速度上（而非可计算性）远比单磁带机更强大。
但回答你的问题：“空间”这里指的是工作空间，不包括输入和输出。
单磁带机器仍然是多磁带机器，只是只有一条磁带。
这篇论文仅关注决策问题，即输出为单比特的问题。
EDIT：这有道理，因为如果考虑所有具有N个输出的问题，那与“将N个不同的决策问题粘合在一起”（加上一些ε的开销）是等价的。
哦，明白了，这是我的第二猜想。
我一直认为，时间和空间复杂度之间的“反比”关系可以用一个简单的事实来解释：当你有一组具有特定时间和空间复杂度的算法时，如果你限制其中一个参数，另一个参数并不一定（实际上往往不是）是最优的。但这并不一定意味着更快的算法会需要更少的内存，反之亦然。
这种“反比”关系也适用于其他参数。例如在排序算法中，除了时间和空间需求外，还存在稳定性需求。如果你通过稳定性来限制排序算法，那么在性能上你不会获得任何优势（甚至可能会有一些劣势）相比于未受限制的算法。我们可以看到，已知的稳定排序算法要么速度较慢，要么需要更多内存。至今尚未有人发明出性能（包括时间和空间）与非稳定排序算法相当的稳定排序算法。就是这样。
顺便说一句，我非常喜欢《量子杂志》上的许多文章！他们成功地撰写了既能吸引计算机科学专业人士，又能吸引感兴趣的“外行”的文章。他们以鸟瞰视角和非正式的“如何”与“为何”来解释问题，这种风格常常给我带来新的视角和思考方向！
冒着显得荒谬的风险：在计算理论中，是否存在类似“光速”的概念，用来确定内存（空间）与运行时间之间的最终极限？
你是指类似这个 [https://en.wikipedia.org/wiki/Bremermann%27s_limit](https://en.wikipedia.org/wiki/Bremermann%27s_limit) 或这个 [https://en.wikipedia.org/wiki/Quantum_speed_limit](https://en.wikipedia.org/wiki/Quantum_speed_limit) 的概念吗？
哦，等等，我刚刚意识到我刚才说的话可能非常愚蠢：我是在想一些计算复杂度定理，这些定理将内存和运行时复杂度类联系起来，就像“光速”为实际空间和实际时间之间的关系设定了一个最终界限一样。
但光速是最大空间在最短时间内的极限，从计算角度来说，这对应于在最短时间内填充最大量的内存：facepalm：（感谢提供的链接！）
Quanta的诗意风格使得无法理解这意味着什么。熟悉该主题的人能否解释这是否适用于现实世界的计算机，还是仅限于理论情景？这是否意味着即使计算机需要以较低时钟速度运行，我们也需要更多内存？
> 威廉姆斯的证明建立了一种数学程序，可以将任何算法（无论其功能如何）转换为使用更少空间的形式。
好吧，但空间成本低廉，我们通常希望用处理时间来换取空间。
也就是说，恰恰相反。
Ryan 在数学领域最重大的未解决问题之一上取得了一点进展（虽然只是微小的进展）。
他并非试图讨好程序员。
但是什么让一个开放问题变得重要？ 😉
给算法设计师多一点内存，他们就会找到办法缩短时间。
给操作系统开发组织多一点内存，他们就会找到办法恶化响应时间。
这只是提醒我们，内存不仅仅是限制，它是一种资源。
可用的资源（或不可用的资源）及其数量，是使用计算机解决问题时最基本的限制。
你可以确定任何算法的时间复杂度和空间复杂度，如果你需要的话。在某些情况下，你可以调整以获得更多的时间或空间，具体取决于你的特定限制。
更多内容请见第十一章。
在解释P复杂度类时不使用“多项式”一词（“所有可以在合理时间内解决的问题”）对读者来说有点冒犯。
大方一点——这能节省大量时间。一旦你说出“多项式”，读者会想，“比如，任何多项式，甚至像n^100这样的？”你不得不解释，是的，但这仍然比指数级好，等等。他们避免了所有这些
Quanta的目标受众是高于平均水平的人群。因此，我认为让他们提供一两句说明并不为过。甚至一个小图表也能起到奇效。我认为制作一个类似维基百科[0]上的图表并在此环中加入一些方程并不需要太多时间或精力。你也可以通过移除NL并合并EXP来简化。天啊，看看这里的图表[1]。那可是要花更多功夫的。
我认为Quanta不应该害怕向人们展示数学。那才是他们的核心目的。即使我认为他们犯了一些严重的错误，让他们变得不可信……[2]
[0] [https://en.wikipedia.org/wiki/PSPACE#/media/File:Complexity_…](https://en.wikipedia.org/wiki/PSPACE#/media/File:Complexity_subsets_pspace.svg)
[1] [https://www.quantamagazine.org/june-huh-high-school-dropout-…](https://www.quantamagazine.org/june-huh-high-school-dropout-wins-the-fields-medal-20220705/)
[2] [https://news.ycombinator.com/item?id=44067043](https://news.ycombinator.com/item?id=44067043)
我想我的意思是，那些对这个问题感到好奇的读者，要么已经了解复杂性类，要么有能力自己去学习。也许一个简单的链接到类似[https://complexityzoo.net/Petting_Zoo](https://complexityzoo.net/Petting_Zoo)的内容会是一个不错的折中方案。
编辑：Aaronson甚至在关于P的章节中提到了n^100问题。
我不同意，甚至认为这与主题无关。你不知道的事情，就无法对此感到好奇。沟通者的职责是提前铺垫并提供读者不被期望已知的关键信息。如果没有基本的解释，这些术语对读者来说可能就像黑箱一样。
关键在于，一条简单的线[0]和一个简洁的图形就能大幅提升读者的理解，同时为他们提供必要的术语，以便进一步查找相关材料以深化理解。
看看这一行：
“`
| 最重要的类之一被称为“P”。
“`
它几乎没有告诉我们任何信息，除了它的的重要性。接着是：
“`
| 粗略地说，它涵盖了所有可以在合理时间内解决的问题。空间的类似复杂性类被称为“PSPACE”。
“`
这也没有告诉我们任何信息……如果我不知道情况，我的第一反应会是“为什么不直接用PTIME和PSPACE？”
整个研究就是关于连接这两个概念！如果我们不知道要连接的是什么，又如何理解这一点？这就像报道一座连接英格兰和法国的桥梁，却只称其为“桥梁”。它重要吗？从他们谈论的方式来看似乎很重要，但如果没有提供如此关键的背景，又如何知道这种事情的影响？仅仅添加几个词就能获得大量额外背景。
我认为这实际上是一个相当合理的描述，但我还读过《自德谟克利特以来的量子计算》。
遗憾的是，Quanta的链接如此受欢迎，而它们包含了大量围绕数学的伪诗意废话。下面有一个整个帖子来驳斥Quanta文章中引入的误解。
“我认为‘更多空间远胜于更多时间’这一观点非常直观。”（发帖者完全正确）文章中提到：“迄今为止，已知的完成某些任务的算法所需空间量大致与运行时间成正比，研究人员长期认为无法做得更好。”这被解读为时间与空间之间存在比例关系。然而，快速查看复杂性层次结构绝不会暗示这种关系。仔细阅读会发现，文中提到的是“已知算法”用于“特定任务”，那么从这样一个特定陈述中，如何得出普遍的直觉呢？
我是本文的作者。如果你问一位复杂性理论家，他们会告诉你，他们确实对某些问题需要接近线性时间的空间来解决有着普遍的直觉（参见例如Ryan在Scott Aaronson关于该结果的博客文章中的评论#22： [https://scottaaronson.blog/?p=8680](https://scottaaronson.blog/?p=8680)，以及该评论后的讨论）。最直观的理解方式是通过电路/有向无环图（DAG）模型，其中目标是从图的输入节点到达输出节点。某些图非常“宽”：在图的中间某一点进行切割，将有大量边跨越该切割点，每条边都代表计算早期阶段的一些信息，你需要记住这些信息才能到达输出。Ryan 的第一个结果是一种通用方法，可以以渐近上远少于所需空间的成本完成任何计算，即使该计算的图结构看起来像这样。这正是该结果如此令人惊讶的原因！
我的文章在多处明确指出，该结果的普适性/全面性正是其反直觉的核心：
– 在首段中：“内存比计算机科学家所相信的更强大：在所有可想象的计算中，少量内存与大量时间同样有效。”
– 在引言的后半部分，你引用的段落中提到：“迄今为止，已知的所有用于完成_特定任务_的算法所需的空间量都大致与它们的运行时间成正比，研究人员长期以来一直认为无法做得更好。威廉姆斯的证明建立了一种数学方法，可以将_任何算法——无论它做什么_——转换为一种使用空间量少得多的形式。
– 在第三部分中，我明确指出研究人员确实认为空间比时间更强大，具体而言，他们认为空间比时间更强大，而你批评我的文章歪曲了这一观点：“但复杂性理论家怀疑PSPACE是一个更大的类，包含许多不在P中的问题。换句话说，他们认为空间是一种比时间强大得多的计算资源。这种信念源于算法可以反复使用同一小块内存，而时间则没有这么宽容——一旦时间流逝，就无法挽回。”
– 在第四部分，我解释了为什么研究人员认为HPV75的结果无法进一步改进，尽管他们直觉上认为空间比时间更强大，正如上述所言： “_虽然许多问题可以用比时间少得多的空间来解决，但有些问题直觉上似乎需要几乎与时间相当的空间。_”
TCS（以及复杂性理论）是复杂的学科。我花了很多时间采访研究人员，思考如何将我的报道结果提炼成一种形式，使读者无论对该主题的熟悉程度如何都能理解。你当然有权批评我的行文风格、故事叙述方式以及信息呈现的顺序，但我将反驳关于我的文章传播复杂性理论误导信息的指控。你所指的误解，正如你自己承认的，源于你没有仔细阅读。如果你对标题有异议，你也可以对复杂性理论家兰斯·福特诺提出类似的投诉：[https://blog.computationalcomplexity.org/2025/02/you-need-mu…](https://blog.computationalcomplexity.org/2025/02/you-need-much-less-memory-than-time.html) .
感谢你对那条评论的详细回复。我刚刚读了你的文章并很享受，你的回复似乎很准确。
我能想象，将如此复杂的内容传达给广大受众需要付出巨大努力，却要面对这里一群聪明人试图将其拆解，这确实很艰难。
感谢您的善意评价！我也收到过许多令人欣慰的积极反馈。我通常不会与陌生人在线争论，但觉得有必要在此更正记录，以免有人日后看到此内容后误以为“天啊，Quanta完全搞错了”。
在HN上，人们经常抱怨细节的程度，这是公平的！我认为他们往往陷入了关于条件概率的常见谬误。P(“X阅读Quanta”|“X拥有一定的技术背景（大学STEM专业或更高）”)可能比大多数科普杂志更大。但P(‘Y拥有一定的技术背景’|“Y阅读Quanta”)比许多人想象的要低得多。在文章中加入太多技术内容会限制其可读性，而我非常重视内容的可读性。
我认为他们过去做得更好，但现在明显走上了错误的道路。我原本以为那个虫洞事件会让他们完蛋。在整整四个月后才发布编辑注释，这简直是不可原谅的[0])。错误难免发生，但四个月的延迟会摧毁所有可信度。这类问题必须迅速处理！从第一天起就有大牌专家提出严重质疑，这充分表明他们在发布这篇他们明知会很受欢迎的文章前，并未进行充分的外部核查。
这一切所做的只是损害科学信誉。为了个人利益而侵蚀他们赖以谋生的科学基础。这就是为什么美国人（以及其他人）对科学如此缺乏信任。新闻机构，尤其是以科学为重点的新闻机构，不断传播不准确的信息。人们对许多科学话题感到困惑也就不足为奇了，因为除非他们花数年时间成为某一领域的专家，否则很难区分事实与虚构。普通人为什么不应该信任像《Quanta》这样的来源？他们不是“满是专家”吗？真是令人摇头。
[0] 这是我看到的最早带有该注释的存档。如果往前推一天，它就不应该存在了。该文章于2022年11月30日发布，并附带了一段YouTube视频[https://web.archive.org/web/20230329191417/https://www.quant…] (https://web.archive.org/web/20230329191417/https://www.quantamagazine.org/physicists-create-a-wormhole-using-a-quantum-computer-20221130/)
彩虹表大获全胜！
“如果这个问题下周解决，威廉姆斯会后悔莫及。在他写论文之前，他花了几个月时间试图扩展他的结果，但都失败了”
这种想法真奇怪，真悲哀。学术界真是扭曲。
这里未必有什么扭曲之处。我并不认识威廉姆斯，但不认为他会讨厌另一个人，也不认为他对整体进展感到不满，他只是一个真正挑战自己的人，结果却在一周后被超越；为此懊悔不已。
无论如何，这一周尚未结束，至少从量子计算机的文章来看，也许不会有懊悔发生。
我好奇提供树评估算法的研究人员在威廉姆斯提交证明时有何感受。是否因未能更长时间保密成果而感到沮丧，从而错失为这一进展争取功劳的机会？我希望不是这样。