半世纪计算机理论僵局被打破！MIT科学家偶然发现：少量内存节省大量计算时间

白交 发自 凹非寺 量子位 | 公众号 QbitAI 一个计算机领域的著名问题，在停滞50年之后终于有了进展。 MIT科学家威廉姆斯一次偶然发现：证明内存比大家认为的更强大。在所有可以想象的计算中， 少量的内存与大量的时间一样有价值 。 时间和内存（空间）是计算中最基本的两种资源 ，每个算法都需要一些时间来运行，并且在运行时需要一些空间来存储数据。迄今为止，已 知的算法里所需的空间与其运行时间基本上都成正比，研究人员认为没有更好的办法。 但现在威廉姆斯证明，存在一个数学程序，可以将任何算法转换成「占用更少空间」的形式。 由于想法过于不可思议，他当时第一想法是： 大概是自己疯了吧 。 于是开始着手证明自己错了，但想了几个小时也没找出任何瑕疵：没准万一真就自己对了呢。 经过几个月的整理和推敲，最终将成果po到网上，没想到收获大家一种好评。 一华盛顿大学科学家表示： 这是一个相当惊人的结果，也是一个巨大的进步 。 困扰计算机科学家的半世纪难题 先来看看这是一个什么问题。 如果用大白话来讲，这个问题其实源于我们一种直觉： 你可以重复使用空间，但不能重复使用时间 。 算法可以反复使用同一小块内存，而时间却不那么宽容，一 ...