新理論によりコンピューター内部の「時間」と「空間」の常識が崩れ去る / Credit:Canva
これまで、一定数の処理を必要とする計算には、ある一定のメモリが必要と考えられてきました。
そして処理量に対する必要メモリの量は、絶対に減らせないラインが存在するとされていました。
その最たる例が「実際にXステップかかる計算は、X/logXのメモリで実行できる」というものです。
ところが、アメリカのMIT（マサチューセッツ工科大学）で行われた研究によって、その常識を根底から覆しかねない衝撃的な成果が報告されています。
新しい手法を使えば、必要とされるメモリを大幅に減らすことが示されたのです。
まさに「時間と空間が共存する計算の世界」を破壊しかねない大事件と言えるでしょう。
いったいどんな手法が使われ、私たちの未来をどう変えていくのでしょうか？
研究内容の詳細はプレプリントサーバーである『arXiv』にて発表されました。
目次
崩せない時の壁への挑戦ブロック化された計算の“超”省スペース化計算理論の核心に迫る新視点
崩せない時の壁への挑戦
新理論によりコンピューター内部の「時間」と「空間」の常識が崩れ去る / Credit:Canva
計算科学では、「問題を解くために何ステップの時間が必要か」「どれだけのメモリ空間を使うか」という視点が大きな焦点でした。
たとえば1970年代にはすでに「実際にXステップかかる計算は、X/logXのメモリで実行できる」ことが示され、たとえば100ステップを要するプログラムなら、log100=2なので常に50メモリスロット内で実行できる、という目を引く成果が存在しました。
具体的には、時間Xの計算をX/logXの平方根ほどの空間に押し込められる可能性を示唆しています。
つまり、今まで「100ステップの問題なら50スロット」という見方に慣れていた私たちに対し、研究者たちは「いえ、100や50ですらなく、100ステップなら実は15スロットに縮まる可能性があります」とまで語るのです。
このような手法の鍵になっているのは、クックとマーツらが開発した「木構造評価(Tree Evaluation)」という特殊なアルゴリズムです。
膨大な手続きが行われる計算を“ブロック化”し、それらを木のかたちで整理して再帰的に評価することで、想像以上に省メモリを実現できるといいます。
（広告の後にも続きます）
ブロック化された計算の“超”省スペース化
新理論によりコンピューター内部の「時間」と「空間」の常識が崩れ去る / Credit:Canva
今回の「実験」といっても、大量のデータを実際に計算するわけではなく、理論モデル上でのシミュレーションです。
マルチテープを使う計算モデルにおいて、時間ステップ数ttの処理をどれだけ少ない空間で再現できるかを調べました。
まず、計算過程をいくつかのブロックに区切ります。
たとえば数十ステップ単位で切り出して、テープ上の情報の変化も同じように分割していくのです。
すると「○番目のブロックでどのテープのどの部分を参照しているか」などの対応関係がたくさん生まれますが、これを木構造で整理します。
言い換えれば「ブロック間のつながり」をノードとエッジに見立て、最終的な計算結果が木の根（ルート）に集約されるように設計するわけです。
木構造を扱うと、通常は深さに応じてメモリを多く消費しがちですが、クックとマーツらの「木構造評価アルゴリズム」はその部分を劇的に省スペース化してくれます。
数式を使わずにざっくり言うと「必要最低限の部分だけを再帰的に調べる」ことで、ツリーの深さに比例する巨大なメモリを使わずに済むしくみです。
その結果、単純計算では「X/logX空間」が限界と思われてきたのが、「X/logXの平方根でもいけるのでは」との見通しが立ちました。
さらにこの省スペース化を突き詰めると、「そもそも時間を増やす一方がいいのか」「空間をもっと削っても時間的に破綻しないのか」といった問題をあらためて見直す機会にもなります。
従来は「省空間の計算には最低でもこれくらいの時間がかかるはず」という下限がなんとなく言われていましたが、今回の研究でさらに厳密に評価できそうなのです。
計算機科学の理論面と実装面、両方の視点で、この成果が与えるインパクトは小さくありません。
