Claude помог решить задачу 3SUM быстрее O(N²)
Американские исследователи Вирджиния Василевска-Уильямс и Джош Алман опубликовали препринт с алгоритмом решения задачи 3SUM быстрее O(N²). Изначальный алгоритм, по словам авторов, нашла закрытая модель Claude от Anthropic.
- Алгоритм решает задачу 3SUM за O(N¹·⁹⁹⁹²), что быстрее предполагавшегося ранее предела O(N²)
- Вместе с 3SUM ускорилось решение задачи поиска кратчайших путей между всеми парами вершин (APSP)
- По словам авторов, Claude сгенерировал 16 миллионов токенов и нашёл изначальный алгоритм, который учёные затем осознали и улучшили
5 октября американские исследователи Вирджиния Василевска-Уильямс и её бывший аспирант Джош Алман опубликовали на arxiv.org препринт с алгоритмом решения задачи 3SUM за O(N¹·⁹⁹⁹²). Ранее предполагалось, что решить эту задачу быстрее O(N²) невозможно.
Задача 3SUM формулируется просто: есть ли в заданном множестве чисел три, сумма которых равна нулю? Наивное решение с хэш-таблицей и вложенным циклом стоит O(N²). Вопрос о том, можно ли решить её полиномиально быстрее, стоял с 2014 года.
Как пришли к результату
Новый алгоритм построен не напрямую для 3SUM, а через цепочку сведений. Василевска-Уильямс в 2009 году доказала сведение 3SUM к задаче о треугольнике нулевого веса (Exact Triangle), а в 2020-м — сведение Exact Triangle к задаче All-Edges Sparse Triangle. Финальным шагом стало сведение к перемножению узких матриц.
Авторы описывают алгоритм, позволяющий найти значения в любом подмножестве позиций матрицы — но не более определённого числа позиций — за заданное количество арифметических операций. Препринт длиной 76 страниц доступен публично.
Вместе с 3SUM ускорилось и решение задачи нахождения кратчайших путей между любыми парами вершин в графе (All-Pairs Shortest Paths, APSP) — практической задачи вычислительной геометрии.
Роль Claude
По словам авторов препринта, в ходе поиска решений открытых криптографических задач сотрудником Anthropic модель Claude, сгенерировав 16 миллионов токенов, нашла описанный в препринте алгоритм. В сентябре 2026 года Anthropic поделилась им с авторами, добавив NDA, деньги и бесплатный доступ к публичным моделям.
После написания статьи Anthropic применила свою внутреннюю модель для проверки результатов через систему доказательства теорем Lean 4 — формализация также доступна онлайн. Авторы указывают, что использовали помощь Claude в написании текста, создании иллюстраций и проверке математических фактов.
С помощью Claude авторы подготовили и выпустили препринт научной математической статьи длиной 76 страниц меньше чем за месяц от получения письма от Anthropic.
Оговорки
Алгоритм такого класса — по сути многомерный массив с числами. Такие алгоритмы непрактичны из-за сложности и большой константы, скрытой внутри O-нотации. Кроме того, мало кто в мире понимает, как устроен поиск таких алгоритмов.
Для профиТехнические детали: архитектура, цифры, ссылки
Цепочка сведений: 3SUM → Exact Triangle (Василевска-Уильямс, 2009) → All-Edges Sparse Triangle (2020) → перемножение узких матриц размера N×N^r и N^r×N, где r — параметр. Задача 3SUM сводится к перемножению узких матриц, а не к обычному матричному умножению.
Авторы описывают алгоритм поиска значений в любом подмножестве позиций матрицы — но не более определённого числа позиций — за заданное число арифметических операций.
Модель Claude сгенерировала 16 миллионов токенов на выходе. По оценке автора публикации на Хабре, это стоит от силы $1000. Проверка результатов выполнена через систему доказательства теорем Lean 4, формализация доступна онлайн. Препринт — 76 страниц, доступен на arxiv.org.
Вопросы и ответы
- Что такое задача 3SUM?
- Это вопрос, есть ли в заданном множестве чисел три, сумма которых равна нулю. Наивное решение стоит O(N²).
- Какую роль сыграла модель Claude?
- По словам авторов препринта, Claude, сгенерировав 16 миллионов токенов, нашёл изначальный алгоритм. Учёные затем осознали и улучшили его.
- Практичен ли новый алгоритм?
- Нет. Такие алгоритмы непрактичны из-за сложности и большой константы, скрытой внутри O-нотации.
