Операция выполнена!
Закрыть
info@vsetut.pro
Стать автором
Вернуться

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

06.10.2026 14:18:05 | Хабр
Хабы: Математика, Алгоритмы, Искусственный интеллект

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

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

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

Читать далее
Подробнее
Читайте также
НОВОСТИ

ВСЕ НОВОСТИ
ПИШИТЕ

Техническая поддержка проекта ВсеТут

info@vsetut.pro

Copyright © 2026 - vsetut.pro