画期的成果：平方根空間での時間計算量のシミュレーション
2025-02-27
最新の研究によると、時間tで動作する任意の多テープチューリングマシンは、わずかO(√(t log t))の空間でシミュレートできることが示されました。これは、50年前のHopcroftらのO(t/log t)空間シミュレーションを大幅に改善するものです。本研究は、CookとMertzによって最近発見された空間効率の良い木評価アルゴリズムを活用し、時間シミュレーションの問題を、好ましいパラメータを持つ暗黙的に定義された一連の木評価インスタンスに変換します。その結果は、サイズsの制限されたファンイン回路を√s・poly(log s)空間で評価できることを示唆しており、O(n)空間で解けるが、多テープチューリングマシンではn^(2-ε)時間（すべてのε>0に対して）を必要とする問題の存在を示唆しており、P対PSPACE問題にわずかな進歩をもたらしています。
続きを読む