Для алгоритмов память — гораздо более мощный ресурс, чем время

Оригинальная версия этой истории была опубликована в журнале Quanta Magazine .

Однажды июльским днём 2024 года Райан Уильямс решил доказать свою неправоту. Прошло два месяца с тех пор, как он сделал поразительное открытие о взаимосвязи времени и памяти в вычислительной технике. Это был грубый набросок математического доказательства того, что память мощнее, чем полагали специалисты по информатике: небольшое её количество может быть столь же полезным, как и огромное количество времени во всех мыслимых вычислениях. Это звучало настолько неправдоподобно, что он предположил, что что-то не так, и тут же отложил доказательство, чтобы сосредоточиться на менее безумных идеях. Теперь он наконец-то выкроил время, чтобы найти ошибку.

Но этого не произошло. После нескольких часов размышлений над своими аргументами Уильямс не смог найти ни единого изъяна.

«Я думал, что схожу с ума», — сказал Уильямс, учёный-теоретик в области информатики из Массачусетского технологического института. Впервые он задумался о том, что, возможно, только возможно, память действительно настолько сильна, как предполагалось в его работе.

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

«Это потрясающе. Это прекрасно», — сказал Ави Вигдерсон , специалист по теоретической информатике из Института перспективных исследований в Принстоне, штат Нью-Джерси. Узнав об этом, Вигдерсон отправил Уильямсу поздравительное электронное письмо. Тема письма: «Вы меня поразили».

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

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

«Это просто ошеломляющий результат и огромный шаг вперёд», — сказал Пол Бим , специалист по информатике из Вашингтонского университета. «То, что это сделал Райан, уже не так удивительно».

У 46-летнего Уильямса открытое, выразительное лицо и лёгкая седина в волосах. Его кабинет, окна которого выходят на разноцветные шпили Стата-центра Массачусетского технологического института, — ещё один пример креативного использования пространства. Пара ковриков для йоги превратила подоконник в импровизированный уголок для чтения, а стол спрятан в углу необычной формы, освободив место для дивана напротив большой доски, исписанной математическими надписями.

Массачусетский технологический институт находится далеко от дома детства Уильямса в сельской местности Алабамы, где места хватало всем. Он вырос на ферме площадью 50 акров и впервые увидел компьютер в семь лет, когда мать повезла его через весь округ на специальный курс углубленного изучения. Он вспоминал, как его завораживала простая программа для создания цифрового фейерверка.

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

«Я писал программы для себя, на бумаге, чтобы запустить их на будущем компьютере», — сказал он. «Мои родители толком не знали, что со мной делать».

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

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

Уильямса особенно привлекала область теоретической информатики, называемая теорией сложности вычислений. Она занимается ресурсами (такими как время и пространство), необходимыми для решения вычислительных задач, таких как сортировка списков или разложение чисел на множители. Большинство задач можно решить множеством различных алгоритмов, каждый из которых предъявляет свои требования к времени и пространству. Специалисты по теории сложности классифицируют задачи по категориям, называемым классами сложности, на основе ресурсных требований лучших алгоритмов для их решения, то есть алгоритмов, которые работают быстрее всего или используют меньше всего памяти.

Но как сделать изучение вычислительных ресурсов математически строгим? Вы не продвинетесь далеко, если попытаетесь анализировать время и пространство, сравнивая минуты с мегабайтами. Чтобы добиться хоть какого-то прогресса, нужно начать с правильных определений.

Эти определения возникли в результате работы Юриса Хартманиса, пионера компьютерной науки, имевшего опыт работы в условиях ограниченных ресурсов. Он родился в 1928 году в знатной латышской семье, но его детство было прервано началом Второй мировой войны. Советские оккупационные войска арестовали и казнили его отца, а после войны Хартманис окончил среднюю школу в лагере беженцев. Он поступил в университет, где преуспел в учёбе, хотя и не мог позволить себе учебники.

«Я компенсировал это тем, что делал очень подробные записи на лекциях», — вспоминал он в интервью 2009 года . «Есть определённое преимущество в импровизации и преодолении трудностей». Хартманис иммигрировал в Соединённые Штаты в 1949 году и перебивался случайными заработками — собирал сельскохозяйственную технику, производил сталь и даже работал дворецким, одновременно изучая математику в Университете Канзас-Сити. В дальнейшем он сделал впечатляющую и успешную карьеру в молодой области теоретической информатики.

В 1960 году, работая в исследовательской лаборатории General Electric в Скенектади, штат Нью-Йорк, Хартманис познакомился с Ричардом Стернсом, аспирантом, проходившим летнюю стажировку. В двух новаторских работах они сформулировали точные математические определения времени и пространства. Эти определения дали исследователям необходимый язык для сравнения этих двух ресурсов и классификации задач по классам сложности.

Один из важнейших классов носит скромное название «P». Грубо говоря, он охватывает все задачи, которые можно решить за разумное время. Аналогичный класс сложности для пространства называется «PSPACE».

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

«Интуиция настолько проста, — сказал Уильямс. — Пространство можно использовать повторно, но время — нет».

Но интуиции недостаточно для теоретиков сложности: им нужны строгие доказательства. Чтобы доказать, что PSPACE больше P, исследователям пришлось бы показать, что для некоторых задач в PSPACE быстрые алгоритмы категорически невозможны. С чего бы им вообще начать?

Так случилось, что они начали свою деятельность в Корнеллском университете, куда Хартманис перешёл в 1965 году, чтобы возглавить недавно созданный факультет компьютерных наук. Под его руководством факультет быстро стал центром исследований в области теории сложности, и в начале 1970-х годов два исследователя, Джон Хопкрофт и Вольфганг Пауль, поставили перед собой задачу установить точную связь между временем и пространством.

Хопкрофт и Пол знали, что для решения проблемы P и PSPACE им придётся доказать, что определённые вычисления невозможно выполнить за ограниченное время. Но доказать обратное сложно. Вместо этого они решили перевернуть проблему с ног на голову и исследовать, что можно сделать с ограниченным пространством. Они надеялись доказать, что алгоритмы с определённым бюджетом пространства могут решать все те же задачи, что и алгоритмы с чуть большим бюджетом времени. Это означало бы, что пространство как минимум немного мощнее времени — небольшой, но необходимый шаг к доказательству того, что PSPACE больше P.

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

Разработчики алгоритмов давно изучали эти компромиссы между пространством и временем для конкретных задач, таких как сортировка. Но чтобы установить общее соотношение между временем и пространством, Хопкрофту и Полу требовалось нечто более всеобъемлющее: процедура моделирования, экономящая пространство, которая подходит для любого алгоритма, независимо от решаемой им задачи. Они ожидали, что эта универсальность будет иметь свою цену. Универсальная симуляция не может учитывать детали какой-либо конкретной задачи, поэтому она, вероятно, не сэкономит столько места, как специализированная симуляция. Но когда Хопкрофт и Пол начинали свою работу, не существовало никаких известных универсальных методов экономии пространства. Даже небольшая экономия была бы прогрессом.

Прорыв произошёл в 1975 году, когда Хопкрофт и Пол объединились с молодым исследователем Лесли Валиант . Трио разработало универсальную процедуру моделирования , которая всегда экономит немного места. Какой бы алгоритм вы ни использовали, вы получите эквивалентный алгоритм, бюджет памяти которого будет немного меньше бюджета времени исходного алгоритма.

«Всё, что можно сделать за такое-то время, можно сделать и в чуть меньшем пространстве», — сказал Валиант. Это был первый важный шаг на пути к объединению пространства и времени.

Но затем прогресс застопорился, и теоретики сложности начали подозревать, что наткнулись на фундаментальное препятствие. Проблема заключалась именно в универсальном характере симуляции Хопкрофта, Пола и Вэлианта. Хотя многие задачи можно решить, используя гораздо меньше пространства, чем времени, некоторым интуитивно казалось, что для этого потребуется почти столько же места, сколько и времени. Если это так, то более эффективное с точки зрения пространства универсальное моделирование было бы невозможно. Пол и двое других исследователей вскоре доказали, что это действительно невозможно , если принять одно, казалось бы, очевидное предположение: разные блоки данных не могут одновременно занимать одно и то же место в памяти.

«Все считали само собой разумеющимся, что лучшего сделать нельзя», — сказал Вигдерсон.

Результат Пола предполагал, что решение проблемы P против PSPACE потребует полного отказа от моделирования в пользу другого подхода, но ни у кого не возникло хороших идей. Так проблема и стояла 50 лет, пока Уильямс наконец не нашёл выход из тупика.

Сначала ему нужно было закончить колледж.

В 1996 году Уильямсу пришло время подавать документы в колледжи. Он знал, что изучение теории сложности уведёт его далеко от дома, но родители ясно дали понять, что Западное побережье и Канада не рассматриваются. Среди оставшихся вариантов Корнеллский университет выделялся для него своим выдающимся вкладом в историю его любимой дисциплины.

«Этот парень, Хартманис, определил классы сложности времени и пространства», — вспоминает он свои мысли. «Это было важно для меня».

Уильямс был принят в Корнеллский университет благодаря щедрой финансовой помощи и прибыл туда осенью 1997 года, намереваясь сделать всё возможное, чтобы стать специалистом по теории сложности. Его целеустремлённость выделяла его среди однокурсников.

«Он был просто супер-пупер в теории сложности», — сказал Скотт Ааронсон , специалист по информатике из Техасского университета в Остине, который пересекался с Уильямсом в Корнелле.

Но ко второму курсу Уильямс уже с трудом справлялся с предметами, где упор делался на математическую строгость, а не на интуицию. Получив среднюю оценку по теории вычислений, он посоветовал ему рассмотреть другие варианты карьеры. Но Уильямс не отказался от своей мечты. Он усердно работал и поступил на курс теории вычислений в магистратуре, надеясь, что отличная оценка по более сложному курсу будет выглядеть впечатляюще в его заявлении о поступлении в магистратуру. Этот курс преподавал Хартманис, к тому времени уже опытный государственный деятель в этой области.

Уильямс начал каждую неделю посещать занятия Хартманиса, где он почти всегда был единственным студентом, приходившим на занятия. Его упорство окупилось: он получил оценку «отлично» за курс, и Хартманис согласился консультировать его по независимому исследовательскому проекту в следующем семестре. Их еженедельные встречи продолжались на протяжении всего обучения Уильямса в колледже. Хартманис поощрял его развивать индивидуальный подход к исследованиям сложности и мягко выводил из тупиковых ситуаций.

«Тогда он оказал на меня огромное влияние, — сказал Уильямс. — Думаю, и сейчас это влияние на меня тоже».

Но, несмотря на получение желанной аспирантской исследовательской стипендии от Национального научного фонда, Уильямс получил отказ во всех докторских программах, на которые подавал заявки. Узнав об этом, Хартманис позвонил коллеге, а затем поздравил Уильямса с зачислением в годичную магистратуру Корнелла. Год спустя Уильямс снова подал заявки в различные докторские программы, и, имея за плечами этот дополнительный исследовательский опыт, добился успеха.

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

Проблема P против PSPACE в их число не входила. Уильямс был захвачен этой проблемой с тех пор, как впервые столкнулся с ней в колледже. Он даже дополнил свою программу по информатике курсами логики и философии, ища вдохновения в других точках зрения на время и пространство, но безуспешно.

«Это всегда было где-то в глубине моей памяти, — сказал Уильямс. — Я просто не мог придумать ничего достаточно интересного, чтобы рассказать об этом».

В прошлом году он наконец нашел возможность, которой ждал.

История нового результата Уильямса началась с прогресса в другом вопросе, связанном с памятью в вычислениях: какие задачи можно решить при крайне ограниченном пространстве? В 2010 году пионер теории сложности Стивен Кук и его коллеги предложили задачу, названную задачей оценки дерева (tree Evaluation Problem) , которая, как они доказали, была невыполнима для любого алгоритма с бюджетом памяти ниже определённого порога. Но существовала лазейка. Доказательство основывалось на том же здравом предположении, которое Пол и его коллеги сделали десятилетиями ранее: алгоритмы не могут хранить новые данные в уже заполненном пространстве.

Более десятилетия специалисты по теории сложности пытались закрыть эту лазейку. Затем, в 2023 году, сын Кука Джеймс и исследователь Ян Мерц разрушили её, разработав алгоритм , который решил задачу оценки дерева, используя гораздо меньше памяти, чем кто-либо мог себе представить. Доказательство Кука-старшего предполагало, что биты данных подобны камешкам, которые должны занимать отдельные места в памяти алгоритма. Но оказывается, что это не единственный способ хранения данных. «На самом деле, мы можем представить себе эти камешки как объекты, которые мы можем слегка сплющить друг на друга», — сказал Бим.

Алгоритм Кука и Мерца пробудил любопытство многих исследователей, но было неясно, можно ли его как-то применить за пределами задачи оценки дерева. «Никто не понимал, насколько он важен для сравнения времени и пространства», — сказал Вигдерсон.

Райан Уильямс был исключением. Весной 2024 года группа студентов представила презентацию о работе Кука и Мерца в качестве своего итогового проекта на занятиях, которые он вёл. Их энтузиазм вдохновил его изучить её внимательнее. Как только он это сделал, ему в голову пришла идея. Он понял, что метод Кука и Мерца — это действительно универсальный инструмент для сокращения использования пространства. Почему бы не использовать его для создания новой универсальной симуляции, связывающей время и пространство, — подобной той, что разработали Хопкрофт, Пол и Вэлиант, но лучше?

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

В течение 50 лет исследователи считали, что улучшить универсальную симуляцию Хопкрофта, Пола и Вэлианта невозможно. Идея Уильямса, если бы она сработала, не просто побила бы их рекорд, а уничтожила бы его.

«Я подумал об этом и подумал: „Ну, это просто не может быть правдой“», — сказал Уильямс. Он отложил это в сторону и не возвращался к этому до того рокового дня в июле, когда он попытался найти изъян в аргументации и потерпел неудачу. Поняв, что изъяна нет, он потратил месяцы на то, чтобы написать и переписать доказательство, чтобы сделать его максимально понятным.

В конце февраля Уильямс наконец опубликовал готовую работу в интернете . Кук и Мерц были удивлены не меньше всех остальных. «Мне пришлось долго гулять, прежде чем я смог что-то сделать», — сказал Мерц.

Вэлиант во время утренней поездки на работу увидел предварительный обзор улучшения Уильямсом своего результата десятилетней давности. Он много лет преподаёт в Гарвардском университете, расположенном неподалеку от офиса Уильямса в Массачусетском технологическом институте. Они встречались раньше, но не знали, что живут в одном районе, пока не столкнулись в автобусе снежным февральским днём, за несколько недель до публикации результата. Уильямс рассказал о своём доказательстве изумлённому Вэлианту и пообещал прислать ему свою работу.

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

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

«Мне до сих пор трудно в это поверить, — сказал Уильямс. — Это кажется слишком хорошим, чтобы быть правдой».

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

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

«Это может стать настоящей проблемой, а может, и 50-летней», — сказал Валиант. «А может, это будет проблема, которую, возможно, удастся решить уже на следующей неделе».

Если задача будет решена на следующей неделе, Уильямс будет корить себя. Прежде чем написать статью, он потратил месяцы, безуспешно пытаясь расширить свой результат. Но даже если такое расширение невозможно, Уильямс уверен, что дальнейшее исследование космоса обязательно приведёт к чему-то интересному — возможно, к прогрессу в решении совершенно другой проблемы.

«Я никогда не могу доказать именно то, что хочу доказать», — сказал он. «Но часто то, что я доказываю, оказывается гораздо лучше того, что я хотел».

Примечание редактора: Скотт Ааронсон является членом консультативного совета журнала Quanta Magazine.

Оригинальная история перепечатана с разрешения журнала Quanta Magazine , редакционно-независимого издания Фонда Саймонса , миссия которого заключается в повышении уровня понимания науки среди общественности путем освещения научных разработок и тенденций в области математики, физических и биологических наук.