計算複雑性理論における時間対空間の50年問題が解決

計算複雑性理論の中心的な問題は、PとPSPACEの関係です。Pは妥当な時間で解ける問題のクラス、PSPACEは妥当な空間で解ける問題のクラスです。直感的には、空間は時間よりも強力な資源です。なぜなら、空間は再利用できるからです。50年間、研究者たちはPSPACEがPより大きいことを証明しようと試みてきました。つまり、高速アルゴリズムでは解けないが、限られた空間で解ける問題が存在することを証明しようとしてきました。Hopcroft、Paul、Valiantは1975年にブレークスルーを達成し、空間は時間よりもわずかに強力であることを示しました。しかし、この進歩は「シミュレーション」アプローチの限界によって制限されていました。Ryan Williamsがついにこの長年の問題を解決する革新的なアプローチを考案しました。