Для алгоритмов небольшой объем памяти значительно превосходит большой объем времени.

«Потрясающее» доказательство одного учёного-программиста — это первый за 50 лет прогресс в решении одного из самых известных вопросов в информатике. Комментарий Сохранить статью Прочитать позже

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

Всё было не так. После нескольких часов тщательного анализа своего аргумента Уильямс не смог найти ни единого изъяна.

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

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

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

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

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

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

Пространство для прогулок

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

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

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

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

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

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

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

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

Проявление находчивости

Эти определения возникли благодаря работе Юриса Хартманиса, выдающегося учёного-компьютерщика, имевшего опыт работы в условиях ограниченных ресурсов. Он родился в 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 году пионер теории сложности Стивен Кук и его коллеги изобрели задачу, называемую задачей оценки дерева, и доказали, что она невыполнима для любого алгоритма с объемом памяти ниже определенного порога. Но была лазейка. Доказательство основывалось на том же самом здравом предположении, которое Пол и его коллеги сделали десятилетиями ранее: алгоритмы не могут хранить новые данные в уже заполненном пространстве.

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

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

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

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

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

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

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

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

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

PSPACE: Последний рубеж

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

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

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

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

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

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

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

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

Источник: www.quantamagazine.org