√f(n)メモリのみを使用して、時間f(n)にかかるアルゴリズムを実行できます。 ライアン・ウィリアムズによるこの新しい論文は、はるかに少ないメモリを使用して時間制限のあるチューリングマシンをシミュレートする方法を示しています。 STOC 2024 のツリー評価に関する最近の研究を使用して、スペースのニーズを時間の平方根に削減します。