ПОДОБРАТЬ ЧИСЛА С НУЖНОЙ СУММОЙ ПОЧТИ ТАК ЖЕ БЫСТРО, КАК ИХ ПРОЧИТАТЬ

Вот головоломка, которую может сформулировать каждый. У вас есть список целых чисел — скажем, 3, 9, 14, 20 — и цель, скажем, 23. Можно ли выбрать несколько из них так, чтобы их сумма точно равнялась цели? (Здесь можно: 3 + 20 или 9 + 14.) Это задача о сумме подмножеств (Subset Sum), одна из самых фундаментальных задач информатики. Статья описывает её как фундаментальную NP-полную задачу — из семейства задач, известных тем, что их трудно решить точно.

Однако есть лазейка. Если числа не слишком велики, хитроумные алгоритмы работают за время, зависящее от их величины. Классический метод Беллмана 1957 года требует времени, пропорционального количеству чисел n, умноженному на цель t. С тех пор алгоритмы не переставали улучшаться:

• Писингер (1999): пропорционально n × N, где N — наибольшее число;
• Брингман (2017): примерно n + t;
• несколько команд (2021–2024): примерно n + N^(5/3), затем n + N^(3/2).

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

В шаге от цели

Линь Чэнь, Юйчэнь Мао и Гочуань Чжан из Чжэцзянского университета в Китае предлагают алгоритм, работающий за время n + N^(1+ε), где ε — любое малое положительное число, зафиксированное заранее: 0,1, 0,01, 0,001. Он детерминированный, допускает отрицательные числа и повторяющиеся значения и снабжён математическим доказательством. Авторы называют это время почти оптимальным.

Результат обобщается на векторы: выбор элементов так, чтобы несколько сумм одновременно попали в свои цели, за время N^(d+ε) для d координат. Это, в свою очередь, отвечает на часть вопроса, поставленного несколькими группами, о целочисленном программировании — поиске целочисленных решений систем уравнений с ограниченными переменными. Явно разобраны два следствия: разбиение набора чисел на две равные половины и как можно более равномерное распределение заданий между двумя одинаковыми машинами.

Поднять числа в большую размерность

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

Их пример — множество {11, 12, 22, 24}. Запишите 11 и 22 как один и два шага вдоль первой оси, а 12 и 24 — как один и два шага вдоль второй. Тогда возможные суммы заполняют все точки маленького квадрата 4 на 4. Но сплющите этот квадрат обратно на прямую — вычислив 11x + 12y, — и суммы образуют семь отдельных скоплений с промежутками между ними, разбросанных от 0 до 69. Промежутки — иллюзия проекции; в двух измерениях структура проста.

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

Как строилось доказательство

Статья открывается «оговоркой об ИИ». Основной путь доказательства авторы разработали сами, опираясь на собственные недавние работы о плотных многомерных вариантах задачи. Затем они использовали ИИ-модель GPT Astra Ultra, чтобы превратить эти идеи в полные математические доказательства. Модель застряла на нескольких леммах, которые были решены с помощью идей авторов; ход бесед задокументирован в публичной исследовательской заметке. Когда базовый рандомизированный алгоритм был готов, модель распространила его на детерминированные и многомерные варианты «без какого-либо руководства со стороны авторов». Модель также подготовила черновик статьи и, как пишут авторы, проверила её основные результаты доказательством в системе доказательств Lean 4. Авторы берут на себя полную ответственность за содержание.

Ещё не финишная черта

Показатель степени равен 1 + ε, а не ровно 1, и скрытые константы растут по мере уменьшения ε; зависимость от числа измерений не оптимизирована. Сами авторы называют алгоритм «весьма запутанным». Работа теоретическая: в ней нет ни реализации, ни замеров производительности.