Модель Anthropic опровергла гипотезы 3SUM и APSP: впервые получены алгоритмы быстрее квадратичного и кубического времени

Исследовательская модель Anthropic самостоятельно нашла новый алгоритм тонкого умножения матриц, что позволило получить детерминированные алгоритмы для задач 3SUM и APSP со временем, строго меньшим n^2 и n^3 соответственно. Это первое полиномиальное улучшение над классическими оценками, при этом основные теоремы формализованы в системе Lean.