Математики пробили барьер в задаче 3SUM — в выкладках помогали языковые модели

Математики Вирджиния Василевска-Уильямс и Джош Алман выложили препринт с алгоритмом для задачи 3SUM — найти в наборе чисел три, дающих в сумме ноль, — работающим за время порядка N^1,9992 вместо привычного N². Барьер в N² считался практически непреодолимым и служил опорой для оценок сложности десятков других задач.

По словам авторов, часть выкладок помогали делать языковые модели.

Выигрыш пока теоретический: показатель степени ниже двойки на восемь тысячных, на реальных размерах данных это не даёт выигрыша по времени. Значение в том, что барьер пробит, и построенные на нём оценки других задач теперь не абсолютны.