Модель Anthropic нашла алгоритм, опровергший гипотезы 3SUM и APSP
Алгоритм решает 3SUM за O(n^1.9992), а APSP за O(n^2.9995), впервые дав полиномиальное улучшение учебных методов.
Anthropic передала результат авторам, а после написания статьи ее модель формально проверила основные доказательства в Lean.
Один алгоритм для тонких матричных произведений также ускоряет ряд задач через известные редукции.
Почему важно
ИИ уже участвует не только в проверке, но и в получении результатов, на которых держались целые цепочки оценок сложности.