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

[NewsMaker]

Исследование показало, что даже занятое хранилище может быть полезным.

---

---

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что дальше?​

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

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

</section>