これまで、一定数の処理を必要とする計算には、ある一定のメモリが必要と考えられてきました。
そして処理量に対する必要メモリの量は、絶対に減らせないラインが存在するとされていました。
その最たる例が「実際にXステップかかる計算は、X/logXのメモリで実行できる」というものです。
ところが、アメリカのMIT(マサチューセッツ工科大学)で行われた研究によって、その常識を根底から覆しかねない衝撃的な成果が報告されています。
新しい手法を使えば、必要とされるメモリを大幅に減らすことが示されたのです。
まさに「時間と空間が共存する計算の世界」を破壊しかねない大事件と言えるでしょう。
いったいどんな手法が使われ、私たちの未来をどう変えていくのでしょうか?
研究内容の詳細はプレプリントサーバーである『arXiv』にて発表されました。
目次
- 崩せない時の壁への挑戦
- ブロック化された計算の“超”省スペース化
- 計算理論の核心に迫る新視点
崩せない時の壁への挑戦

計算科学では、「問題を解くために何ステップの時間が必要か」「どれだけのメモリ空間を使うか」という視点が大きな焦点でした。
たとえば1970年代にはすでに「実際にXステップかかる計算は、X/logXのメモリで実行できる」ことが示され、たとえば100ステップを要するプログラムなら、log100=2なので常に50メモリスロット内で実行できる、という目を引く成果が存在しました。
具体的には、時間Xの計算をX/logXの平方根ほどの空間に押し込められる可能性を示唆しています。
つまり、今まで「100ステップの問題なら50スロット」という見方に慣れていた私たちに対し、研究者たちは「いえ、100や50ですらなく、100ステップなら実は15スロットに縮まる可能性があります」とまで語るのです。