Сложные вычисления — в минимальном объёме памяти

По закону Мура плотность транзисторов на микросхеме удваивается каждые 24 месяца. Производительность CPU, GPU, TPU и NPU растёт уже несколько десятилетий, что привело нас вплотную к задачам эмуляции мозга и Сверхинтеллекта.

Когда-то компьютеры занимали целые комнаты, а сегодня у каждого в кармане маленький «суперкомпьютер». Но специалисты по теории информации решают фундаментальный вопрос: сколько места (памяти) нужно в теории, чтобы выполнить задачу? Этот вопрос лежит в основе понятия вычислительной сложности.

Вычислительная сложность или просто «сложность» в информатике означает объём ресурсов для вычисления задачи. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений.

Каждый алгоритм требует определённых ресурсов для вычисления. У него есть два ресурса — время (вычислительные циклы CPU, ) и пространство (память, ). Так мы учитываем временну́ю сложность алгоритма и пространственную сложность.

Временна́я и пространственная сложность алгоритма обычно выражается с использованием математической нотации «O» большое. Например, , , , , где n является характеристикой входных данных, которые влияют на сложность.

Итак, у нас время и память. Но как они зависят друг от друга? Правда ли, что любая задача, которая решается в полиномиальном пространстве , также решается в полиномиальном ? И как они могут друг друга заменять?

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

С момента публикации фундаментальной научной работы Джона Хопкрофта с соавторами «О соотношении времени и пространства» (“On Time Versus Space”) 1977 года считалось, что при увеличении сложности задачи (количество шагов алгоритма) пропорционально растёт и объём необходимой памяти. Таково было интуитивно понятная зависимость.

Только недавно выяснилось, что «конвертация сложности» работает иначе. И на самом деле требуется не t памяти, а всего лишь .

P ≠ PSPACE

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

Аналогично и полиномиальное время описывает задачи, которые можно решить за ограниченное время.

Вопрос в том, насколько эти два класса пересекаются. Другими словами, насколько мы можем пожертвовать памятью ради производительности — и наоборот. Каков теоретический предел, в какое минимальное «пространство» можно втиснуть вычисления заданной сложности? И как растёт потребление памяти при увеличении сложности задачи?

На протяжении 50-ти лет учёные бьются над проблемой P ≠ PSPACE. За это время они смогли доказать только то, что если задача требует t шагов, то решение возможно с использованием примерно бит памяти. Но лишь в малом классе задач. Что будет дальше, при увеличении сложности?

Всегда предполагалось, что дальше зависимость тоже соблюдается. Грубо говоря, если задача требует в сто раз больше шагов, то она потребует в сто раз больше памяти.

Но оказалось, что логика здесь не действует. Всё работает иначе.

Неожиданное решение

В прошлом году на симпозиуме ACM по теории вычислений в Праге была официально представлена работа, которая вносит неожиданный поворот в эту задачи. Автор статьи Райан Вильямс из Массачусетского технологического института доказал, что любая задача, решаемая за время , требует не , а всего около бит памяти! То есть в сто раз сложнейший алгоритм можно решить, увеличив объём памяти всего в десять раз! Это стало ошеломительным открытием для индустрии.

«Этот результат показывает, что интуитивный подход совершенно неверный, — сказал Уильямс в комментарии журналу Quanta Magazine. — Я сначала даже подумал, что-то неправильно [в моём доказательстве], потому что вывод совершенно неожиданный».

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

«Такой прогресс невероятен, — говорит Махди Черагчи (Mahdi Cheraghchi) из Университета Мичигана. — Раньше были задачи, решаемые за определённое время, но многие считали, что это нельзя сделать в столь крошечном пространстве».

Доказательство

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

Требуется показать, что существует задача линейного пространства, которую нельзя решить за времени для любого постоянного .

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

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

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

Далее автор доказывает теорему, что для любой функции выполняется правило:

Для доказательства этой теоремы автор использует хитрую структуру в виде дерева вычислений (Tree Evaluation), а именно — недавно открытый свежий алгоритм для этого дерева.

Вот доказательство по шагам:

1. Разбиваем работу многоленточной машины Тьюринга на блоки по b шагов, а ленты — на блоки по b ячеек.

2. Строим абстрактное дерево вычисления. Каждый узел дерева соответствует тому, что происходит с некоторым блоком ленты за b шагов. Дети каждого узла — предыдущие блоки, от состояния которых он зависит.

3. Получается задача вида Tree Evaluation. Каждая внутренняя вершина дерева — это функция от значения детей, а листья — исходные данные. Нам нужно узнать значение в корне.

4. Тут самое главное, с точки зрения вычисления. Автор использует опубликованный в 2012 году алгоритм Кука–Мерца для Tree Evaluation, который умеет считать значение в корне в очень маленькой памяти:

где h — высота дерева, b — размер значения в узле, d — число детей узла.

Подбирая длину блока b, то есть балансируя высоту дерева и размер значений, автор получает как раз значение используемой памяти примерно .

Таким образом, любой алгоритм из t шагов на многоленточной машине Тьюринга можно симулировать, используя всего памяти, точнее, .

Как говорилось в известной книге «Programming Perl»: «Если у вас кончилась память, её можно докупить, но если кончилось время — у вас проблема» (в вольном переводе).

За работы по нижним оценкам вычисляемости алгоритмов Райан Уильямс получил премию Гёделя 2024 года, есть видеозапись лекции на церемонии в Таллине, где он рассказывает о своих исследованиях (с 18-й минуты). Вышеупомянутая статья Уильямса «Симуляция времени в квадратном корне пространства» 2025 года непосредственно вытекает из этих исследований:

Эффективность использования памяти

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

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

• MicroQuickJS от Фабриса Беллара — движок JavaScript для встроенных систем. Он компилирует и выполняет программы на JavaScript, используя всего 10 КБ оперативной памяти. В ПЗУ движок с библиотекой на С занимает 100 КБ (код ARM Thumb-2). При этом скорость компиляции и выполнения кода сопоставима с QuickJS, это предыдущая разработка Фабриса Беллара, тоже минималистичный JS-движок, для x86 систем: только файлы С, никаких зависимостей: демо, бенчмарки 1 и 2.

Эти примеры показывают, что сложные вычислительные задачи действительно можно упаковать в минимальное количество памяти.

Научная статья «Симуляция времени в квадратном корне пространства» («Simulating Time With Square-Root Space») опубликована 25 февраля 2025 года к симпозиуму ACM по теории вычислений в Праге (arXiv:2502.17779).

© 2026 ООО «МТ ФИНАНС»