量子位
·
半世纪计算机理论僵局被打破！MIT科学家偶然发现：少量内存节省大量计算时间
💡
原文中文，约4000字，阅读约需10分钟。
📝
内容提要
MIT科学家威廉姆斯意外发现，少量内存可以显著减少计算时间，解决了计算机科学中停滞50年的难题。他证明了可以将任何算法转化为占用更少空间的形式，挑战了传统的时间和空间观念。这一发现被视为计算复杂性理论的重要进展。
🎯
关键要点
- MIT科学家威廉姆斯发现少量内存可以显著减少计算时间，解决了计算机科学中停滞50年的难题。
- 威廉姆斯证明可以将任何算法转化为占用更少空间的形式，挑战了传统的时间和空间观念。
- 时间和内存是计算中最基本的资源，传统观点认为空间与运行时间成正比。
- 复杂性理论是计算机科学的一个分支，研究算法所需的资源。
- 20世纪60年代，哈特马尼斯建立了分析时间和空间的精确定义，提出了P和PSPACE的概念。
- 科学家们认为PSPACE是一个更大的类，包含许多P中没有的问题。
- 威廉姆斯在2010年受到树评估问题的启发，发现数据可以在内存中更有效地存储。
- 他提出的算法可以将空间占用减少到原始算法时间预算的平方根。
- 威廉姆斯的发现被视为计算复杂性理论的重要进展，可能改变对时间和空间的理解。
- 威廉姆斯的研究经历了多次挫折，但最终取得了突破，成为该领域的重要人物。
❓
延伸问答
威廉姆斯的发现对计算机科学有什么影响？
威廉姆斯的发现被视为计算复杂性理论的重要进展，挑战了传统的时间和空间观念，可能改变对计算资源的理解。
威廉姆斯是如何证明内存可以减少计算时间的？
威廉姆斯证明可以将任何算法转化为占用更少空间的形式，提出的算法可以将空间占用减少到原始算法时间预算的平方根。
计算复杂性理论的核心问题是什么？
计算复杂性理论的核心问题是研究算法所需的资源，特别是时间和空间之间的关系。
P与PSPACE之间的关系是什么？
P类问题可以在合理时间内解决，而PSPACE类问题则是一个更大的类，包含许多P中没有的问题，科学家们认为空间是一种比时间更强大的计算资源。
威廉姆斯的研究经历了哪些挑战？
威廉姆斯的研究经历了多次挫折，特别是在证明PSPACE大于P的问题上，最终在2010年和2023年取得突破。
威廉姆斯的发现如何改变传统观念？
威廉姆斯的发现挑战了传统观点，即空间与运行时间成正比，表明少量内存可以显著减少计算时间。
➡️
