Sie können jeden Algorithmus ausführen, der Zeit f(n) benötigt, und dabei nur √f(n) Speicher verwenden. Dieses neue Papier von Ryan Williams zeigt, wie man zeitlich begrenzte Turingmaschinen mit deutlich weniger Speicher simulieren kann. Es nutzt aktuelle Arbeiten von STOC 2024 zur Baum-Evaluierung, um den Speicherbedarf auf die Quadratwurzel der Zeit zu reduzieren.