时间与空间：计算复杂性理论的50年难题终获突破

计算复杂性理论的核心问题之一是P与PSPACE的关系。P类问题能在合理时间内解决，PSPACE类问题则在合理空间内解决。直觉上，空间比时间更强大，因为空间可重复利用，但时间不可逆。50年来，研究者们试图证明PSPACE大于P，即存在一些问题，在有限时间内无法解决，却可在有限空间内解决。Hopcroft, Paul和Valiant在1975年取得突破，证明空间比时间略强。然而，这一进展受限于“模拟”方法的局限性。直到Ryan Williams打破僵局，另辟蹊径，最终攻克了这一难题。