新理論によりコンピューター内部の「時間」と「空間」の常識が崩れ去る (2/3)

ブロック化された計算の“超”省スペース化

今回の「実験」といっても、大量のデータを実際に計算するわけではなく、理論モデル上でのシミュレーションです。

マルチテープを使う計算モデルにおいて、時間ステップ数ttの処理をどれだけ少ない空間で再現できるかを調べました。

まず、計算過程をいくつかのブロックに区切ります。

たとえば数十ステップ単位で切り出して、テープ上の情報の変化も同じように分割していくのです。

すると「○番目のブロックでどのテープのどの部分を参照しているか」などの対応関係がたくさん生まれますが、これを木構造で整理します。

言い換えれば「ブロック間のつながり」をノードとエッジに見立て、最終的な計算結果が木の根（ルート）に集約されるように設計するわけです。

木構造を扱うと、通常は深さに応じてメモリを多く消費しがちですが、クックとマーツらの「木構造評価アルゴリズム」はその部分を劇的に省スペース化してくれます。

数式を使わずにざっくり言うと「必要最低限の部分だけを再帰的に調べる」ことで、ツリーの深さに比例する巨大なメモリを使わずに済むしくみです。

その結果、単純計算では「X/logX空間」が限界と思われてきたのが、「X/logXの平方根でもいけるのでは」との見通しが立ちました。

さらにこの省スペース化を突き詰めると、「そもそも時間を増やす一方がいいのか」「空間をもっと削っても時間的に破綻しないのか」といった問題をあらためて見直す機会にもなります。

従来は「省空間の計算には最低でもこれくらいの時間がかかるはず」という下限がなんとなく言われていましたが、今回の研究でさらに厳密に評価できそうなのです。

計算機科学の理論面と実装面、両方の視点で、この成果が与えるインパクトは小さくありません。