「速く計算するには多くのメモリが必要」という50年来の常識を覆す？ 米MIT教授が新理論 査読前論文を発表：Innovative Tech

米国マサチューセッツ工科大学（MIT）のRyan Williams教授は、コンピュータが計算処理を行う際の「時間」と「空間」の関係性について、従来の理論を大幅に改善するという研究報告（査読前のプレプリント）を発表した。

[山下裕毅，ITmedia]

Innovative Tech：

このコーナーでは、2014年から先端テクノロジーの研究を論文単位で記事にしているWebメディア「Seamless」（シームレス）を主宰する山下裕毅氏が執筆。新規性の高い科学論文を山下氏がピックアップし、解説する。

X： ＠shiropen2

　米国マサチューセッツ工科大学（MIT）のライアン・ウィリアムズ教授が発表した論文「Simulating Time With Square-Root Space」は、コンピュータが計算処理を行う際の「時間」と「空間」の関係性について、従来の理論を大幅に改善するという研究報告（査読前のプレプリント）である。速く計算するには多くのメモリが必要という50年来の常識を覆す可能性を示す。

米MIT教授がメモリに関する新理論を発表

　計算機科学で「時間」とはコンピュータが実行する処理ステップの数を意味し、「空間」とは計算に必要なメモリ使用量を指す。

　約50年前の1970年代、チューリングマシンが時間tを要する計算は空間O（t/log t）で実行可能であることを証明した。しかし、今回の新しい研究によれば、同じ時間tの計算は、わずかO（√（t log t））という驚くほど少ない空間で実行可能であることを示している。

　これは、計算ステップ数が増大しても、必要なメモリ量が従来の理論よりも大幅に少なくて済むことを意味している。また計算の規模が大きくなるほど、この差はさらに拡大する。

　この理論を可能にしたのは「木構造評価」（Tree Evaluation）と呼ばれる問題に対する最近のアルゴリズム進展である。ウィリアムズ教授はこの新しいアルゴリズムを応用し、複雑な計算をより単純な木構造の評価問題に変換することで、記憶領域の大幅な削減を実現した。

論文のトップページ

　この結果は、計算理論における「P対PSPACE問題」という長年の未解決問題に一助を与える可能性がある。また回路の評価が、従来考えられていたよりも大幅に少ないメモリで可能であることも示した。

Source and Image Credits: Williams, R. Ryan. “Simulating Time With Square-Root Space.” arXiv preprint arXiv:2502.17779（2025）.