麻省理工学院计算机科学教授 Ryan Williams 认为，少量内存“在所有可以想象的计算中，其作用与大量时间一样大……”《量子》杂志写道。“今年二月，他终于将他的证明发布到网上，获得了广泛赞誉……”每个算法都需要一定的运行时间，并且在运行时需要一定的空间来存储数据。到目前为止，唯一已知的完成某些任务的算法所需的空间量大致与其运行时间成正比，而研究人员长期以来一直认为没有更好的方法。Williams 的证明建立了一种数学程序，可以将任何算法（无论其功能是什么）转换为占用空间更少的形式。更重要的是，这个结果——关于在给定一定空间的情况下可以计算什么的陈述——也暗示了第二个结果，即在一定时间内无法计算什么。第二个结果本身并不令人惊讶：研究人员期望它是正确的，但他们不知道如何证明它。 Williams 的解决方案基于他的第一个结果，感觉有点夸张，就像要通过为地球上的所有人提供铁证如山的不在场证明来证明一名嫌疑犯有罪一样。它或许还能为攻克计算机科学中最古老的开放性难题之一提供一种新思路。“这是一个相当惊人的结果，也是一个巨大的进步，”华盛顿大学计算机科学家 Paul Beame 说道。感谢 Slashdot 的长期读者 mspohr 分享这篇文章。
在 Slashdot 上阅读更多内容。