従来は「省空間の計算には最低でもこれくらいの時間がかかるはず」という下限がなんとなく言われていましたが、今回の研究でさらに厳密に評価できそうなのです。
計算機科学の理論面と実装面、両方の視点で、この成果が与えるインパクトは小さくありません。
計算理論の核心に迫る新視点

こうした「木構造評価による省メモリシミュレーション」は、これまでの定説を大きく揺るがす可能性があります。
もっとも、すべての計算モデルにそのまま適用できるわけではありません。
たとえば、ランダムアクセス型(RAM)のマシンではメモリへのアクセスパターンが複雑化するため、まったく同じ手法が通じるかどうかは未知数です。
しかし「もしRAMでも似たような省スペース化が達成できれば、アルゴリズム全般が飛躍的に効率化するかもしれない」と多くの研究者が注目しています。
さらに、このアプローチが「PとPSPACEの分離」という壮大な目標に近づく手がかりになるのではないか、という期待も生まれています。
ただし、理論的にも簡単に結論が出るものではありません。
木構造評価アルゴリズム自体にも多くの拡張や改良の余地があり、まだ「X/logXの平方根が本当に限界かどうか」すらはっきりしないからです。
研究者自身が「100ステップの問題を50スロットどころか15スロットに落とせるかも」と口にするように、今後さらなる発見があるかもしれません。
とはいえ、すでに見えてきた成果だけでも、大規模な回路を少ないメモリ空間で評価できる可能性がわかったり、分岐プログラム(branching program)のサイズを劇的に削減できたりと、応用範囲は非常に広いと考えられます。
今後もこうした理論を踏まえたアルゴリズム設計や下限の研究が進めば、P対PSPACEといった古くからの難問にも新しいアプローチが可能になるでしょう。