Você pode executar qualquer algoritmo que leve tempo f(n) usando apenas memória √f(n). Este novo artigo de Ryan Williams mostra como simular máquinas de Turing com limite de tempo usando muito menos memória. Ele usa trabalhos recentes do STOC 2024 sobre Avaliação de Árvores para reduzir as necessidades de espaço à raiz quadrada do tempo.