Десять лет назад исследователи доказали, что добавление в компьютер уже заполненной памяти теоретически может помочь вычислениям. Сейчас они только начинают понимать, к чему это может привести.
«Очевидно» — опасное слово, даже в сценариях, которые кажутся простыми. Предположим, например, что вам нужно произвести важные вычисления. Вы выбираете между двумя почти одинаковыми компьютерами, за исключением того, что в одном из них есть дополнительный жёсткий диск, заполненный драгоценными семейными фотографиями. Естественно предположить, что эти два варианта одинаково хороши — дополнительный диск, на котором не осталось места, не поможет вам в вычислениях.
«Очевидно, что это не поможет, верно?» — говорит Бруно Лофф, специалист по информатике из Лиссабонского университета.
Ошибаетесь. В 2014 году Лофф и четверо других исследователей обнаружили, что добавление заполненного накопителя в принципе может сделать компьютер более мощным. Их теоретическая схема, названная каталитическими вычислениями, стала самостоятельным объектом для изучения. А недавно она помогла исследователям получить поразительный результат в смежной области компьютерной науки: стандартный подход к решению главного открытого вопроса о роли памяти в вычислениях, скорее всего, зашёл в тупик.
«Это настоящий подвиг, — сказал Пьер Маккензи, специалист по теории сложности из Монреальского университета. — Я очень ценю эти результаты».
Почти без памяти
Каталитические вычисления выросли из работ по теории сложности вычислений — отрасли информатики, посвящённой ресурсам, необходимым для решения различных задач. Все проблемы, которые рассматривают теоретики сложности, могут быть решены с помощью пошаговых процедур, называемых алгоритмами. Но алгоритмы не одинаковы – одни, к примеру, работают быстрее других, или занимают меньше места в памяти компьютера. Теоретики сложности сортируют проблемы на различные классы, основываясь на поведении лучших алгоритмов, известных для их решения.
Самый известный класс, получивший название «P», содержит все задачи, для которых известны быстрые алгоритмы, такие как поиск наименьшего числа в списке или поиск кратчайшего пути между двумя точками в сети. Другой класс, называемый «L», устанавливает более высокую планку для вступления в него: у задач из L должны быть алгоритмы, которые не только быстро работают, но и почти не используют память. Одним из примеров является задача «наименьшее число в списке». По определению, каждая проблема из L также входит в P, но исследователи давно задаются вопросом, верно ли обратное.
«Основной вопрос — "Могу ли я взять любую задачу из P и решить её, используя очень, очень мало памяти?"», — говорит Маккензи.
Большинство исследователей полагают, что ответ на этот вопрос отрицательный. Чтобы доказать это, им нужно выбрать конкретную задачу из P и показать, что её невозможно решить с помощью любого хитроумного трюка по экономии памяти.
В конце 2000-х годов Маккензи и специалист-новатор теории сложности Стивен Кук придумали задачу, которая казалась многообещающим кандидатом. Названная проблемой оценки дерева, она включает в себя многократное решение более простой математической задачи, которая превращает пару входных чисел в одно выходное. Копии этой математической задачи располагаются слоями, как матчи в турнирной таблице: входные данные каждого слоя становятся входными данными следующего слоя, пока не останется только один выход. Различные алгоритмы оценки дерева представляют собой разные стратегии вычисления конечного выхода из начальных входов — они могут выполнять вычисления в другом порядке или по-другому записывать результаты промежуточных шагов.
Многие алгоритмы могут быстро решить проблему оценки дерева, что относит её к классу P. Но каждый такой алгоритм должен выделить некоторое количество памяти для значений, с которыми он работает, а также хранить уже вычисленные значения для использования на последующих шагах. Поэтому Кук и Маккензи подозревали, что проблему невозможно решить с помощью ограниченной памяти. Они формализовали это предположение в работе 2010 года, написанной в соавторстве с тремя другими исследователями, и доказали, что каждый обычный алгоритм решения проблемы оценки дерева требует слишком много памяти, чтобы претендовать на членство в L.
Однако их работа не исключала возможности существования причудливых алгоритмов, которые могли бы каким-то образом использовать один и тот же участок памяти для хранения и вычислений одновременно — вычислительный эквивалент использования страницы, заполненной важными заметками, в качестве писчей бумаги. Кук и Маккензи считали, что таких необычных алгоритмов не может существовать, и были достаточно уверены, чтобы поставить на это деньги: тот, кто докажет, что они ошибаются, выиграет $100.
Каталитическое преобразование
Михал Коуки (Michal Koucký), теоретик сложности из Карлова университета в Праге, узнал о результатах этой оценки деревьев от Кука во время академического отпуска в Торонто в 2011 году. Он твёрдо решил завершить начатое Куком и Маккензи, доказав, что нет способа произвести дополнительные вычисления, используя память, которая сохраняет данные на потом. Поиски Коуки привели его к неожиданному открытию каталитических вычислений. Почти десять лет спустя это открытие вдохновит двух молодых исследователей вернуться к оценке деревьев и раз и навсегда разрешить спор Кука и Маккензи.
Но вернёмся к истории каталитических вычислений. Всё началось с того, что Коуки посетил своих коллег в Амстердаме и задал вопрос, который его волновал, в более простой формулировке: что можно сделать с памятью, которая уже заполнена?
Очевидным ответом было «ничего». «Я подумал: "Ладно, это, конечно, совершенно бесполезно, и мы собираемся это доказать", — говорит Гарри Борман, руководитель амстердамской группы. — А потом мы не смогли доказать это».
Прорыв произошёл несколько месяцев спустя, когда Борман был в гостях у своего частого соавтора Ричарда Клива в Университете Ватерлоо. Они решили сосредоточиться на экстремальном сценарии, когда полная память очень велика. Если компьютер с небольшим объёмом свободной памяти сможет получить доступ к этой огромной забитой памяти, позволит ли это ему решать задачи, которые были бы невозможны при использовании только свободной памяти? Это похоже на вопрос о «жёстком диске, полном семейных фотографий», только этот жёсткий диск размером с центр обработки данных.
Если эти дополнительные данные неприкосновенны — вы не можете с ними взаимодействовать — то они определённо не помогут. Но что, если вам разрешат подправить некоторые биты, кодирующие эти данные, при условии, что вы пообещаете сбросить их, когда закончите? Вы не можете просто хранить запись о своих изменениях, поскольку это займёт ещё больше места, поэтому вам придётся убедиться, что ваши изменения легко обратимы. Более того, вы не можете выбирать содержимое дополнительных данных, поэтому всё, что вы сделаете, должно работать при любой возможной начальной конфигурации битов.
Это довольно жёсткие ограничения, поэтому было неочевидно, что дополнительная память может оказаться полезной. Но, к своему удивлению, Борман и Клив показали, что при правильной настройке битов из заполненной памяти действительно можно извлечь дополнительную вычислительную мощность.
«Это был шок для всех», — говорит Лофф, который в то время был аспирантом в группе Бурмана и работал над вопросом памяти вместе со своим сокурсником Флорианом Спилманом. Вскоре команда расширила результат на ещё более широкий класс задач и в 2014 году опубликовала объединённые результаты.
Они назвали новый фреймворк каталитическими вычислениями, позаимствовав термин из химии. «Без катализатора реакция бы не пошла, — говорит Рагхунатх Тевари, теоретик сложности из Индийского технологического института в Канпуре. — Но сам катализатор остаётся неизменным».
Недалеко от дерева
Небольшая группа исследователей продолжала развивать каталитические вычисления, но никто даже не пытался применить их к проблеме оценки деревьев, которая изначально вдохновила Коуки на поиски. Для этой задачи оставался открытым вопрос, можно ли использовать небольшой объём памяти для хранения и вычислений одновременно. Но методы каталитических вычислений предполагали, что дополнительная заполненная память должна быть очень большой. Уменьшите объём этой памяти, и методы перестанут работать.
Тем не менее, один молодой исследователь не смог удержаться от вопроса, есть ли способ адаптировать эти методы для повторного использования памяти в алгоритме оценки деревьев. Его звали Джеймс Кук, и проблема оценки деревьев была для него личной: Стивен Кук, легендарный теоретик сложности, который её придумал, — его отец. Джеймс даже работал над ней в аспирантуре, хотя в основном занимался совершенно несвязанными с ней темами. К тому времени, когда в 2014 году он познакомился с оригинальной статьёй о каталитических вычислениях, Джеймс уже собирался закончить университет и уйти из науки, чтобы заняться разработкой программного обеспечения. Но даже освоившись на новой работе, он продолжал думать о каталитических вычислениях.
«Мне нужно было понять это и разобраться с тем, что можно было сделать», — сказал он.
В течение нескольких лет Джеймс Кук в свободное время занимался разработкой каталитического подхода к решению проблемы оценки деревьев. В 2019 году он рассказал о своих успехах на симпозиуме, посвящённом новаторской работе его отца в области теории сложности. После доклада к нему подошёл аспирант по имени Ян Мерц, который влюбился в каталитические вычисления пятью годами ранее, узнав о них, будучи впечатлительным молодым студентом.
«Это было похоже на то, как у птенца происходит импринтинг», — говорит Мерц.
Кук и Мерц объединили усилия, и вскоре их старания окупились. В 2020 году они разработали алгоритм, который решал проблему оценки деревьев с меньшим объёмом памяти, чем необходимый минимум, предположенный старшими Куком и Маккензи, хотя он был лишь ненамного ниже этого порога. Тем не менее, этого хватило, чтобы выплатить $100; к счастью для Куков, половина этих денег осталась в семье.
Но работы было ещё много. Исследователи начали изучать оценку деревьев, потому что казалось, что она может наконец-то дать пример задачи в P, которой нет в L — другими словами, относительно лёгкой задачи, которую нельзя решить, используя очень мало памяти. Новый метод Кука и Мерца использовал меньше памяти, чем любой другой алгоритм оценки деревьев, но всё равно значительно больше, чем любой алгоритм для задач в L. Оценка деревьев была в минусе, но не в проигрыше.
В 2023 году Кук и Мерц представили улучшенный алгоритм, который использовал гораздо меньше памяти — едва ли больше, чем максимально допустимый для задач в L. Многие исследователи теперь подозревают, что оценка деревьев всё-таки входит в L, и что доказательство этого — лишь вопрос времени. Теоретикам сложности может понадобиться другой подход к проблеме «P против L».
Тем временем результаты Кука и Мерца вызвали интерес к каталитическим вычислениям, и в новых работах изучаются связи со случайностью и влияние допущения нескольких ошибок на возвращение полной памяти к исходному состоянию.
«Мы ещё не закончили изучать возможности этих новых методов, — говорит Маккензи. — Возможно, нас ждёт ещё больше сюрпризов».
Автор: SLY_G
