Каталитические вычисления: как заполненная память может ускорить работу компьютера

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

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

Как мало памяти достаточно?

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

Самый известный класс — "P" — включает задачи, которые можно решить быстро, например, нахождение наименьшего числа в списке или кратчайшего пути между двумя точками. Другой класс — "L" — требует, чтобы алгоритмы использовали минимальный объём памяти. Например, нахождение наименьшего числа в списке возможно без значительных затрат памяти, поэтому эта задача принадлежит к классу L. Однако остаётся вопрос: можно ли любую задачу из P решить, используя минимальное количество памяти?

Учёные считают, что ответ — "нет", но чтобы доказать это, необходимо найти задачу, которая требует больше памяти, чем позволяет класс L.

Задача, которая не поддавалась

В конце 2000-х годов Пьер Маккензи и Стивен Кук , один из пионеров теории вычислительной сложности, предложили такую задачу. Они назвали её "задачей оценки дерева". Её суть — в вычислении итогового значения, используя серию промежуточных операций, организованных в виде турнирной сетки. Разные алгоритмы могут решать эту задачу по-разному, но всем им требуется сохранять промежуточные результаты.

Учёные предположили, что решить эту задачу, используя крайне малый объём памяти, невозможно. В своей статье 2010 года они доказали, что любой стандартный алгоритм требует слишком много памяти, чтобы попасть в класс L.

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

Неожиданный прорыв

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

Исследователи показали, что если можно временно модифицировать часть данных в памяти, не изменяя её окончательное состояние, это создаёт новый вычислительный ресурс. Эти методы легли в основу каталитических вычислений .

Задача оценки дерева решена?

В 2020 году Джеймс Кук (сын Стивена Кука) и Иэн Мерц применили принципы каталитических вычислений к задаче оценки дерева и смогли доказать, что она решаема с меньшим объёмом памяти, чем считалось ранее. Этот результат не только опроверг прежние теоретические догадки, но и позволил Куку выиграть $100 — приз, обещанный его отцом.

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

Что дальше?

Каталитические вычисления уже вызвали интерес у исследователей. Теперь учёные изучают, как этот метод можно применить в других областях, включая квантовые вычисления, случайные алгоритмы и методы хранения данных. Как отмечает Маккензи, "мы только начали понимать возможности этих методов, и впереди нас ждут новые открытия".

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