Вы можете запустить любой алгоритм, который требует времени f(n) , используя только √f(n) памяти. Эта новая работа Райана Уильямса показывает, как смоделировать машины Тьюринга с ограничением по времени, используя гораздо меньше памяти. Она использует недавние работы из STOC 2024 по оценке деревьев, чтобы сократить потребности в памяти до квадратного корня от времени.