quanta 停滞50年的计算机领域著名问题，如今有了怎样的进展？

quanta 停滞50年的计算机领域著名问题，如今有了怎样的进展？

一个计算机领域的著名问题，在停滞50年之后终于有了进展。

麻省理工学院的威廉姆斯科学家在一次偶然的实验中观察到：证实了存储器的性能远超人们的普遍认知。在所有我们能够设想出的计算任务中，有限的存储资源与充裕的计算时间具有同等的重要性。

时间与内存构成了计算过程中的两大基础要素，任何算法在执行过程中都不可避免地要消耗一定的时间，同时还需要占用一定的空间以存放相关信息。

截至目前，所有已知的算法在所需存储空间和运行时间上均呈现出一种相对的线性关系，研究者普遍认为，目前尚无更优的解决方案。

目前，威廉姆斯已经证实，有一个数学程序能够将任何算法转化为占用空间更小的版本。

由于想法过于不可思议，他当时第一想法是：大概是自己疯了吧。

于是他开始努力证明自己的错误，然而经过数小时的深思熟虑，并未发现任何破绽；或许，说不定他真的就是对的。

经过数月的精心整理与反复琢磨，成果终于得以发布至网络平台，未曾想，竟赢得了众人的广泛赞誉。

华盛顿大学的科研人员指出，这一发现令人震惊，同时也代表了显著的进展。

困扰计算机科学家的半世纪难题

先来看看这是一个什么问题。

简单来说，这个问题的根源在于我们的一种基本感觉：空间是可以被反复利用的，而时间却是无法重复的。

算法能够多次利用同一片内存空间，然而时间却并不宽容，一旦流逝，便无法重新获得。

但对于正经科学家来说，直觉是不够的，这需要严谨的证明！

哎，这就难到科学家了，没成想一难就难了半世纪。（Doge）

威廉姆斯所在的领域是计算机科学一个分支学科计算复杂性理论。

该领域涵盖了处理如列表排序、因式分解等计算任务所需的各种资源，比如时间与空间。

多数问题均能采用多样化的算法来处理，而这些算法在处理过程中对时间与空间资源的需求各不相同。复杂性理论研究者们依据最优算法——即运行速度最为迅速或空间占用最小的算法——的资源消耗情况，将问题细分为众多类别，这些类别被称作复杂性类别。

然而，我们该如何确保计算资源的研究达到数学上的严格标准呢？若仅局限于对时间和空间进行剖析，这显然是不切实际的。

要想取得进展，首先需要正确的定义。

在20世纪60年代，计算机领域的专家哈特马尼斯创立了一套精确的定义，该定义旨在对时间和空间进行深入分析。

P，囊括了所有在合理时间范围内能够得到解决的问题。在空间领域，与之相对应的复杂度类别被称作“”。

这两类问题间的联系构成了复杂性理论的核心议题之一。在P类问题中，每一个问题均归属于此类，因为即便是快速算法，也难以在有限的时间内将计算机内存中的广阔空间完全填满。

若情况相反亦然，则这两个类别将等同：空间与时间将具备相等的计算效能。

科学家们对此持有疑虑，他们推测这可能是更大范畴的一部分，其中蕴含着P所未能涵盖的众多问题。换言之，他们相信空间相较于时间，是一种更为强大的计算工具。

为确保大于P的成立，研究者需证实，在特定问题上，不存在任何一种算法能够迅速解决。

1965年，哈特马尼斯移居至康奈尔大学，并肩负起新设计算机科学系主任的重任。在他的带领下，该系迅速崛起，成为复杂性理论领域的核心研究机构。

在20世纪70年代初期，那两位科研工作者约翰·霍普克罗夫特与沃尔夫冈·保罗开始致力于构建时间和空间之间的精确关系。

他们明白，若要解决 P 与 之间的难题，关键在于证实某些计算在有限时间内无法实现。然而，这一证明过程极具挑战性。

于是，他们选择从另一个角度审视这个问题，研究在空间受限的条件下可以实现哪些功能。他们期望证实，在限定空间资源的前提下，算法能够处理那些在时间资源上略有宽裕的算法所能处理的所有问题。

这显示出空间至少略优于时间——这构成了证明 P 大于 的一小步且不可或缺的环节。

为了达成这一目标，他们采取了一种“模拟”策略，这一策略涉及将现有的算法转换成适用于同样问题的全新算法，尽管在所需的空间和耗费的时间上存在差异。

有一个大家都能理解的例子，你掌握了一种高效的方法，能够按照字母顺序对书架上的书籍进行整理，不过这要求你将书籍分成数十个小堆。或许你更倾向于选择一种占用公寓空间较少的方案，尽管这样做可能会耗费更多的时间。

模拟涉及一种数学运算，通过这一过程，你可以获得更为高效的算法方案；输入原有的算法模型，系统将输出一种新的算法，这种新算法在节省存储空间的同时，可能会在一定程度上影响运算速度。

他们二人希望建立一个通用的模拟软件，该软件能够兼容所有算法，哪怕仅仅是为了节省微小的空间。到了1975年，在一位名叫瓦利安特的年轻研究员的协助下，他们三人最终将这一构想付诸实践。

瓦利安特

然而，不久之后，进展遭遇了瓶颈，复杂性理论学者们开始对所面临的可能是根本性的难题产生疑虑。症结在于模拟的广泛适用性和普遍性。

尽管许多难题在占用较少空间的情况下就能得到解决，然而，某些问题在直观上似乎需要与时间相当的空间来处理。

而且，当时的作者保罗及其合著者迅速证实，普遍适用性根本无法达成。

于是这个问题就这样持续了50年都没有解决。

威廉姆斯是怎么解决的？

1996年，他来到了康奈尔大学，追随哈特马尼斯的脚步。

自大学初次遭遇此问题，他便对此产生了浓厚的兴趣，以至于在主修计算机科学之余，他还选修了逻辑学及哲学课程，期望能在不同的时空维度中找到启示，然而，尽管努力不懈，他终究未能取得任何实质性的进展。

2010年，在计算记忆领域又取得了一次突破性的进展：那时，人们开始探讨哪些问题能够在极小的空间内得到有效解决。

2010年，复杂性理论的开拓者Cook及其团队提出了一种称作“树评估问题”的挑战。他们成功论证了，若算法的空间限制低于某一特定界限，则无法达成该目标。然而，在此过程中，他们发现了一个漏洞。

该证明基于保罗及其团队成员多年前所提出的普遍性观点，即算法无法将新增数据存入已满的存储空间。

过去十余年间，研究人员持续努力修复这一缺陷。到了2023年，Cook之子及其合作者成功研发出一项算法，有效解决了树木评估难题，且其所需存储空间远低于人们原先的预期。

老Cook把数据比喻作鹅卵石，指出它们无法被压缩，且必须在算法的内存中各占一席之地。然而，实际情况表明，这并非存储数据的唯一途径。我们可以将这些鹅卵石设想为可以略微挤凑在一起的物质。

威廉姆斯在一堂课上灵光乍现：

哎呀，既然数据能够被压缩，那么这种方法岂不是就可以算作一种能够有效降低空间内存需求的普遍工具了吗？

深入研究后发现，这种模拟技术显著降低了新算法所需的存储空间——其所需空间仅约为原始算法时间预留量的平方根。

这种创新的节省空间算法运行速度较慢，因此，该模拟在现实中可能难以得到应用。然而，从理论层面来看，它无疑具有划时代的意义。

接着，他仅通过几步数学推演，便反证了时间计算能力的一个负面效应：至少存在某些问题，若不投入超过空间的时间，便无法得到解决。这一更为局限的结论与研究人员原先的预期相符。

从定性分析的角度出发，威廉姆斯的这一发现似乎正是众人长久以来梦寐以求的P与问题解决方案的体现。

两者的区别在于规模。

P和属于一个涵盖范围极广的复杂度类别，与此同时，威廉姆斯的研究成果是在更为细致的层面上展开的。

为了证实大于P的结论，研究人员需对现有差距进行更大程度的拓宽。然而，威廉姆斯历经数月尝试进行拓展，却始终未能成功。

半个世纪以前投身于通用模拟研究的瓦利安特研究员，如今在哈佛大学执教，他这样说道：

这可能是一个终极瓶颈，也可能是一个持续50年的瓶颈。

又或者下周就可能解决。

大二老师曾劝他转方向

尽管如今46岁的他已取得显著成就，然而回顾过去，他曾在几十年前遭受过老师对其学习方向的调整。

威廉姆斯在阿拉巴马州乡村度过了他的童年时光，那里坐落着一个占地50英亩的农场。

七岁那年，他首次目睹了电脑的神奇，那是在母亲驾驶车辆载他穿越县城，前往一个别具一格的学术强化班时。他后来回忆道，当时一款能够制作数字烟花效果的简易程序，深深地吸引了他。

随机挑选一种色彩，随即将其从屏幕中心向任意一个随机方向投射出去。你无法预知，最终将呈现出一幅怎样的画面。

那时起，他对编程产生了极大的热情，甚至在没有计算机的情况下，也会在纸上编写程序，这让父母感到十分困惑，不知如何是好。

在高中后两年阶段，他转学至阿拉巴马的数学与科学学校，这所学校让他首次接触到了计算机科学的理论，并且，他也首次明确了自己想要从事的事业。

我察觉到外界的世界更为辽阔，并且掌握了运用数学思维来解析计算机的技巧。

到了申请大学的关键时刻，他意识到若要深入研究复杂性理论，必须离开故土，然而他的父母却坚决反对，认为前往西海岸或加拿大是不可能实现的。在众多选择中，康奈尔大学最终成为了他的首选。

他凭借着丰厚的经济支持，踏入了这片梦寐以求的土地，来到了这个理论的摇篮——康奈尔大学。

然而进入大二之后，他发现自己难以跟上课程进度。在计算理论这门课上，他仅取得了中等水平的成绩，老师便建议他思考是否应该考虑其他职业道路。

他坚决拒绝，选择付出更多努力，选修了一门研究生理论课程，期望在这门更具挑战性的课程中取得卓越成绩，以便在研究生申请阶段显得格外出众。

讲授该研究生课程的教师是哈特马尼斯教授，当时他已是该领域内的资深专家。

威廉姆斯开始每周都参加哈特马尼斯开设的办公室课程，他几乎是唯一一个准时出席的学生。他的持之以恒最终得到了回报：他在课程中取得了优异的成绩，获得了A等，而且哈特马尼斯还答应在下一个学期为他提供指导，帮助他完成一个独立的研究项目。

在大学时光里，他们二人定期相约见面。哈特马尼斯积极引导他，助他形成独特的复杂性问题研究路径，同时指导他走出思维定势的困境。

自那时起，他一直致力于复杂性理论的研究。到了2010年，他取得了一项具有划时代意义的成就，这一成就被视为在解决P与NP问题道路上迈出的重要一步。

这一成就进一步确立了威廉姆斯的声望，紧接着，他又陆续发表了多篇探讨复杂性理论多个议题的学术论文。

然而，这个问题始终萦绕在他的心头：我实在想不出什么足够吸引人的内容。

这就是真·念念不忘，必有回响吧。

参考链接：