Vous pouvez exécuter n'importe quel algorithme qui prend du temps f(n) en utilisant seulement √f(n) mémoire. Ce nouvel article de Ryan Williams montre comment simuler des machines de Turing à temps borné en utilisant beaucoup moins de mémoire. Il utilise des travaux récents de STOC 2024 sur l'évaluation d'arbres pour réduire les besoins en espace à la racine carrée du temps.