50年僵局打破！MIT最新证明：对于算法少量内存胜过大量时间

MIT 的 Ryan Williams 开发出一种新方法，可将任意算法转化为占用显著更少空间的形式，其所需空间大致为运行时间的平方根。这一突破性成果颠覆了过去 50 年关于计算时间和空间关系的传统认知，揭示了空间资源相较于时间更具价值的可能性。同时，该研究间接证明了某些问题无法在有限时间内解决，为复杂性理论中 P 类与 PSPACE 类关系的研究提供了全新视角。
来源：https://mp.weixin.qq.com/s/BBABdpBUVdCV5xhQPdrPmg