Прорыв в теории алгоритмов: задача 3SUM решена быстрее квадратичного времени — помог Claude от Anthropic

5 октября на arxiv.org появился препринт Вирджинии Василевски-Уильямс и её бывшего аспиранта Джоша Алмана. Они заявили об алгоритме, решающем классическую задачу 3SUM за O(N¹·⁹⁹⁹²) — то есть быстрее, чем O(N²), что ранее считалось невозможным. Вместе с этим падает и сложность задачи поиска кратчайших путей между всеми парами вершин (APSP) — практически важной задачи вычислительной геометрии.

Уникальность работы не только в математическом результате, но и в методологии: авторы утверждают, что изначальный алгоритм был найден моделью Claude (Anthropic), после чего учёные осознали его и улучшили. Корректность финальной версии также проверяла закрытая модель Anthropic. Это один из первых случаев, когда LLM сыграла ключевую роль в теоретическом прорыве, а не просто помогла с кодом или текстом.

Для сообщества алгоритмистов это знаковое событие: 3SUM — одна из фундаментальных задач, чья сложность десятилетиями считалась непреодолимой. Если результат подтвердится, он изменит подход к целому классу вычислительных проблем и откроет путь к новым практическим алгоритмам.