PSPACE vs P：空间复杂度超越时间的可能？

计算理论的核心问题之一是P与PSPACE复杂度类之间的关系。P包含可在合理时间内解决的问题，而PSPACE则对应空间复杂度。长期以来，人们普遍认为PSPACE比P更大，因为空间可以复用，而时间却无法逆转。然而，证明这一猜想需要找到PSPACE中无法在多项式时间内解决的问题。文章回顾了Hopcroft, Paul和Valiant在1975年取得的突破，他们证明了空间比时间略强，但随后进展停滞。直到Ryan Williams打破了僵局，他的研究为解决P vs PSPACE问题提供了新的思路。