P対PSPACE：空間計算は時間計算よりも強力か？

計算複雑性理論の中心的な問いは、複雑性クラスPとPSPACEの関係です。Pは妥当な時間内に解ける問題を包含する一方、PSPACEは空間計算量を扱います。PSPACEはPよりも大きいという考え方が一般的ですが、これは時間とは異なり空間が再利用できるためです。これを証明するには、PSPACEの中に多項式時間で解けない問題を示す必要があります。この記事では、1975年にHopcroft、Paul、Valiantが行った画期的な研究、つまり空間が時間よりもわずかに優れていることを示した研究を振り返り、その後進展が停滞したことを述べています。Ryan Williamsの研究がついにこの行き詰まりを打破し、P対PSPACE問題の解決に新たな洞察を与えました。