清华姚班大神，再度引爆理论计算机科学圈！ 50年来，顶尖科学家都在死磕「旅行商问题」等这类计算机复杂性难题，却迟迟没有进展。 为什么一直证明不出来？ 实际上，答案藏在了「元数学」的领域。 恰在去年，一篇名为《Reverse Mathematics Below the Turing Jump》论文低调上线。 作者仅有三个人，清华姚班陈立杰、本科生李嘉图，以及著名计算机领域学者Igor Carboni Oliveira。 论文地址：https://eccc.weizmann.ac.il/report/2024/060/ 他们不再死磕从公理推导定理的传统路径，而是另辟蹊径，采用了「元数学」中「逆向数学」的方法。 结果惊喜地发现，许多看似风马牛不相及的理论，竟在底层逻辑中是完全等价的。 这也让他们越来越多地开始琢磨一个相关但更让人摸不着头脑的问题：为啥证明老是不成功呢？ 比如，「鸽巢原理」与图灵机的「回文下界」。 这篇论文一出，彻底颠覆了人们的「世界观」。 过去半个世纪，计算机科学家们苦苦追求「更强公理证明更难定理」的思路，原来从一开始就走偏了。 把数学「倒过来」 颠覆千年思维范式 一提到那些「硬骨头」难题，计算机科 ...

计算复杂性理论突破 - MIT科学家威廉姆斯发现少量内存与大量时间在计算中具有同等价值，提出数学程序可将算法转换为占用更少空间的形式[2][4] - 该发现挑战了传统认知，即算法空间需求与运行时间成正比的关系被打破[3][14] - 华盛顿大学科学家评价此为"惊人结果和巨大进步"，威廉姆斯本人最初也难以置信[5][7] P与PSPACE难题历史 - 计算机科学界50年来未能证明PSPACE是否严格大于P类问题[8][26] - 20世纪60年代哈特马尼斯定义P类(合理时间解决问题)和PSPACE类(空间复杂度问题)[11] - 1975年霍普克罗夫特、保罗和瓦利安特开发通用模拟程序，但证明普适性不可行后研究停滞[21][25] 威廉姆斯解决方案机制 - 受2023年"树评估问题"突破启发，发现数据可压缩存储，空间占用可降至原始算法时间预算的平方根[28][31] - 通过数学证明至少部分问题必须消耗多于空间的时间才能解决，但尚未扩展到P与PSPACE全域[33][36] - 哈佛教授瓦利安特认为这可能突破50年瓶颈，也可能仍需长期探索[38][39] 研究者背景与学术历程 - 威廉姆斯童年受计算机程序启发，高中确立用数学研究计算机的方向[42][44] - 大二被劝退后师从哈特马尼斯，通过研究生课程逆袭并持续研究复杂性理论[47][51] - 2010年曾解决P与NP问题的子问题奠定学术地位，最终在2023年取得空间-时间关系突破[52][55]