Когда мало — это много: как чуть-чуть памяти заменяет вечность вычислений

Американский теоретик Райан Уильямс (MIT) представил доказательство, которое может изменить представления о фундаментальных ресурсах вычислений — времени и памяти. В своей работе он предложил новый универсальный способ симуляции алгоритмов, который впервые за 50 лет позволил существенно сократить требования к памяти — даже при сохранении полной вычислительной мощности. Его открытие уже называют крупнейшим прорывом в теории вычислительной сложности с 1970-х годов.

В июле 2024 года Уильямс решил перепроверить набросок идеи, которую ранее посчитал слишком безумной, чтобы быть истиной. Доказательство утверждало, что память может быть настолько же мощным вычислительным ресурсом, как и время: небольшое её количество может заменить огромное количество шагов. После тщательного анализа он не нашёл в доказательстве ошибок.

В феврале 2025 года он опубликовал работу на arXiv , вызвав восторг у коллег. Ави Вигдерсон из Института перспективных исследований (Принстон) написал ему с темой письма «You blew my mind». Пол Бим (Университет Вашингтона) назвал результат «ошеломляющим» и отметил, что не удивлён, что его достиг именно Уильямс.

Ключевой вывод работы — возможность преобразовать любой алгоритм так, чтобы он использовал существенно меньше памяти, пусть и за счёт большего времени выполнения. При этом открытие имеет и второй, не менее важный эффект: из него следует, что некоторые вычисления невозможно выполнить за ограниченное время без увеличения объёма памяти — что было ожидаемо, но до сих пор не имело строгого доказательства.

Уильямс вырос на ферме в Алабаме, впервые увидел компьютер в семь лет и сразу увлёкся программированием. В старших классах он поступил в специализированную школу, где познакомился с теорией сложности — областью, изучающей ресурсы, необходимые для решения задач. Позже, поступив в Корнелл, он учился у одного из основателей теории сложности, Юриса Хартманиса, и именно тот стал его наставником.

Теория сложности изучает классы задач, различающиеся по времени и памяти, например, P (быстро решаемые задачи) и PSPACE (решаемые с ограниченной памятью). До сих пор было неясно, насколько мощнее PSPACE, и можно ли это строго доказать. В 1975 году Хопкрофт, Пауль и Вэлиант предложили универсальную симуляцию, экономящую немного памяти, но дальнейший прогресс застопорился: в 1983 году Пауль с коллегами доказали, что улучшить симуляцию невозможно — при определённых допущениях.

Прорыв произошёл после того, как в 2023 году Джеймс Кук и Ян Мерц нашли способ обойти одно из этих допущений, создав алгоритм , использующий «сжимаемые» единицы памяти, как «гибкие камешки». Именно эта идея вдохновила Уильямса.

Он понял, что метод «гибких камешков» можно использовать для создания новой универсальной симуляции, которая сокращает требования к памяти до квадратного корня от исходного времени работы алгоритма. В теории это означает, что пространство действительно мощнее времени. Такой подход может не иметь практического применения из-за роста времени выполнения, но в теоретическом смысле он радикально меняет правила игры.

Лесли Вэлиант, один из авторов классической симуляции, был впечатлён, узнав об открытии от Уильямса в автобусе по пути на работу. «Если у тебя есть результат, лучший за последние 50 лет, ты явно всё делаешь правильно», — сказал он.

Уильямс доказал как положительное утверждение — что небольшое количество памяти может заменить большее количество времени, — так и отрицательное: что при фиксированном времени невозможно решить некоторые задачи без увеличения объёма памяти. Эти результаты ещё не доказывают, что PSPACE больше P, но приближают на шаг к этой цели.

Он надеется, что следующий прорыв может случиться в любую минуту. И хотя сам не смог расширить своё доказательство, он уверен — это только начало. «Я редко доказываю именно то, что хотел, — сказал Уильямс. — Но часто оказывается, что я доказал нечто куда более интересное».