Задача 3SUM решена быстрее, чем за O(N²) — а именно за O(N¹·⁹⁹⁹²). Без нейронок не обошлось

5 октября американские исследователи Вирджиния Василевска-Уильямс, известная своими быстрыми (и безумно сложными) алгоритмами перемножения матриц за вместо и её бывший аспирант Джош Алман опубликовали препринт на arxiv.org, демонстрирующий алгоритм решения задачи 3SUM за .

Это знаковое событие в узких кругах. Во-первых, раньше предполагалось, что решить эту задачу быстрее, чем за , невозможно. Во-вторых, вместе с ней наконец решилась быстрее, чем за , задача нахождения кратчайших путей между любыми парами вершин в графе (All-Pairs Shortest Paths, APSP) — по-настоящему практическая задача вычислительной геометрии. В-третьих, мало того, что корректность работы проверяла закрытая модель Anthropic — авторы также утверждают, что Claude нашёл изначальный алгоритм, после чего учёные осознали и улучшили его.

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

Задача 3SUM

Есть ли в заданном множестве чисел три, сумма которых равна нулю?

Это и есть вся задача. Формулируется в одно предложение, и в целом решается любым мало-мальски тренированным программистом с помощью хэш-таблицы и вложенного цикла за пять минут:

from itertools import combinations

def solve_3sum(numbers: set[int]) -> bool:
    for x, y in combinations(numbers, 2):
        z = -x - y
        if z in present:
            return True
    return False

Нетрудно проверить, что решение это стоит . Сначала (при необходимости) строим хэш-таблицу за , потом пробегаем по всем парам чисел и делаем в неё запрос за . Вопрос, стоявший с 2014 года, был в том, можно ли решить её быстрее — а именно полиномиально быстрее, то есть за для хоть какого-то положительного . Теперь мы знаем, что !

Exact Triangle problem

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

В данном случае это задача о треугольнике нулевого веса, в англоязычной среде известная как Exact Triangle problem.

Есть ли в заданном графе графе с рёбрами с целочисленными весами и вершинами треугольник, сумма весов ребёр в котором равна нулю?

Ещё одна задача с простой формулировкой и наивным решением, в этот раз за , которое не страшно попросить налайвкодить на собеседовании. Сама Вирджиния доказала это сведение (вместе с мужем!) в 2009 году — в тексте всего 19 страниц, все желающие приглашаются к чтению. Причём не просто доказала сведение, а доказала, что если найден алгоритм за , то для 3SUM будет автоматически найден алгоритм за .

All-Edges Sparse Triangle problem

Следующее сведение, снова доказанное Василевска-Уильямс, уже в 2020-м году, сводит Exact Triangle к All-Edges Sparse Triangle.

В заданном графе с рёбрами определить для каждого ребра, входит ли оно в хоть какой-нибудь треугольник.

Наивное решение по-прежнему просто: перебираем все рёбра, перебираем все пары соседних рёбер, проверяем, получается ли треугольник — получаем . Но к чему же сводится эта задача, чтобы получить не наивное?

Перемножение матриц

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

И, конечно, не удивительно, что и здесь всё в итоге пришло к ним — хоть и довольно интересным способом.

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

Назовём эту матрицу (от слова adjacency — смежность). Что будет, если мы, скажем, возведём её в квадрат? Какой будет смысл у числа в ячейке матрицы ? Давайте посмотрим на определение произведения матриц:

По сути мы берём всевозможные промежуточные вершины и перемножаем количество способов попасть из в (за один шаг) на количество способов попасть из в (также за один шаг). А значит, мы перебираем всевозможные способы попасть из в за два шага.

Это легко можно использовать для решения задачи All-Edges Sparse Triangle. Строим матрицу смежности, считаем её квадрат. Дальше перебираем все рёбра графа. Если — ребро в графе, мы точно знаем, что из в можно попасть напрямую за один шаг. Если при этом величина не равна нулю, значит, можно попасть из в за два шага. А это как раз означает, что ребро лежит в каком-то треугольнике . Итого мы решили задачу, возведя матрицу в квадрат.

Чуть более сложным образом, чем я описал (окей, значительно более сложным образом) задача 3SUM сводится Вирджинией к перемножению узких матриц — размера и размера , с . Да не просто перемножению. Учёные описывают алгоритм, позволяющий найти значения в любом подмножестве позиций матрицы — но не более позиций — за арифметических операций.

Препринт с этим результатом публично доступен и длиной всего в 76 страниц — можно прочитать и написать потом хорошую статью на Хабр (ну или сразу кандидатскую диссертацию).

Роль Claude

Авторы препринта рассказывают, что в ходе поиска решений открытых криптографических задач сотрудником Anthropic модель, сгенерировав 16 миллионов токенов, нашла описанный в препринте алгоритм. В сентябре 2026-го Anthropic поделилась им с авторами, докинув NDA, денег и бесплатного доступа к публичным моделям.

После написания статьи Anthropic также применили свою внутреннюю модель для проверки результатов посредством системы доказательства теорем Lean 4 — формализация также доступна онлайн.

Также авторы указывают, что использовали помощь Claude в написании текста, создании иллюстраций (их в статье аж 10 штук) и проверке математических фактов.

Заключение

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

Закрытая модель Anthropic нашла новый алгоритм такого класса за сессию, продолжительность и цену которой сложно оценить — мы знаем только про 16 миллионов токенов на выходе, что стоит от силы $1000.

С помощью Claude авторы подготовили и выпустили препринт научной математической статьи длиной в 76 страниц меньше, чем за месяц от получения письма от Anthropic.

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