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

Core Insights - A significant breakthrough has been made in computer science after a 50-year stagnation regarding the relationship between time and memory in algorithms [1][8]. Group 1: Breakthrough Discovery - MIT scientist Williams discovered that memory is more powerful than previously thought, indicating that a small amount of memory can be as valuable as a large amount of time in computations [2][4]. - Williams proved that there exists a mathematical program that can convert any algorithm into a form that occupies less space [4][7]. Group 2: Historical Context - The problem stems from the intuition that space can be reused, but time cannot, leading to a half-century challenge in proving the relationship between time and space in computational complexity theory [8][10]. - The complexity theory, established in the 1960s, categorizes problems based on the resources (time and space) required to solve them, with P representing problems solvable in reasonable time and PSPACE representing those solvable with limited space [11][13]. Group 3: Theoretical Implications - The relationship between P and PSPACE is a core issue in complexity theory, with scientists historically believing that space is a more powerful computational resource than time [15][19]. - Williams' results suggest that some problems cannot be solved unless more time is used than space, hinting at a potential resolution to the long-standing P vs. PSPACE question [33][34]. Group 4: Personal Journey of the Researcher - Williams has been fascinated by this problem since his university days and has pursued various avenues, including studying logic and philosophy, to find inspiration [27][42]. - His breakthrough was influenced by a 2010 advancement in understanding computational memory, which led him to realize that data could be compressed, allowing for significant reductions in space usage [28][31].