　米国マサチューセッツ工科大学（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）.

「検閲されてないインターネット」を中国の学生1800人に1年半無料で与える実験　2019年に論文発表　その結果は？
中国の北京大学と米ハーバード大学、米MITに所属する研究者らは2019年に、中国の学生に検閲されていないVPN経由のインターネットアクセスを無料で提供した研究報告を発表した。
絡まったケーブルを解くために“最適な振る速度”は？　米国の物理学者が発見
米ジョージア工科大学と米スタンフォード大学、米MITに所属する研究者らは、複数の糸が絡まった塊から1本の糸を解きほぐす最適な方法を提案した研究報告を発表した。
“針穴のへこみ”でデータ保存する新ストレージ　浅い／深いへこみで同じ面積に4倍のデータを記録　加熱で消去
オーストラリアのフリンダース大学に所属する研究者らがは、探針で穴を開けるようにへこみを付けてデータを書き込み、読み取り、消去を可能にするアプローチを提案した研究報告を発表した。
数学の未解決問題「コラッツ予想」を証明？　日本人研究者がプレプリント公開　SNS上でも一部話題に
玉川大学と千葉大学に所属する川崎敏治さん（崎はたつさき）の単著論文「A proof of the Collatz conjecture」がarXivでプレプリント（査読前）として登場した。新たな不動点定理を使用してコラッツ予想を証明したという。
「産業社会で生きる人 vs. 〇〇民族」　睡眠の質がいいのはどっち？　カナダチームが分析
カナダのトロント大学に所属する研究者らは、産業社会と非産業社会における睡眠パターンを比較した研究報告を発表した。