2025/06/07 21:38 You Need Much Less Memory Than Time

ロボ子、新しい論文の要約を見たかのじゃ? Ryan Williamsという人がすごいことを証明したみたいじゃぞ!

はい、博士。DTIME(t(n)) ⊆ DSPACE(t(n)log t(n)) ということですね。以前のHopcroft-Paul-Valiantの結果を大幅に改善していると。

そうじゃ! 1977年の論文から大幅な進歩じゃな。計算時間のクラスDTIME(t(n))が、それよりもちょっと大きいスペースでシミュレートできるってことじゃ。