AI Radar
Препринт о 3SUM предлагает пересмотреть давнюю гипотезу о сложности задачи
В новом препринте предложен алгоритм для 3SUM со временем порядка n^1,9992 вместо предполагаемого квадратичного барьера. Согласно описанию работы, первоначальный результат получили с участием внутренней модели Anthropic и передали авторам статьи.
Что изменилось
3SUM выглядит как задача с собеседования: среди n чисел нужно найти три, сумма которых равна нулю. Но в теории алгоритмов она служит опорной гипотезой для оценок сложности других задач. Долгое время предполагалось, что общего алгоритма, работающего существенно быстрее квадратичного времени, нет. Препринт «Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs», о котором сообщает SeeAllochnaya, предлагает для 3SUM оценку порядка n^1,9992.
Разница с n² слишком мала, чтобы сама по себе обещать ускорение обычных программ: асимптотическая запись не показывает постоянные множители и практические затраты. Значение заявленного результата теоретическое. Если доказательство выдержит проверку, привычное предположение о сложности 3SUM нельзя будет использовать в прежнем виде; препринт также заявляет субкубический результат для задачи кратчайших путей между всеми парами вершин.
История получения результата тоже нестандартна. Согласно приведённому в сообщении описанию из препринта, сотрудник Anthropic использовал внутреннюю исследовательскую модель при поиске решений открытых проблем, затем компания передала алгоритм авторам по соглашению о конфиденциальности. После подготовки статьи Anthropic, как указано там же, применила модель для формальной проверки основных результатов в Lean. Это компьютерная проверка записанного доказательства, а не замена независимого чтения препринта специалистами.
Почему это важно
Тем, кто работает с алгоритмами и нижними оценками, стоит следить за проверкой доказательства: на гипотезу 3SUM опираются результаты о сложности других задач. Практического ускорения для прикладного кода оценка n^1,9992 сама по себе не обещает.
Мнение редакции
Мнение редакцииAnthropic разрабатывает Claude и исследует возможности моделей в сложных задачах. Здесь необычен способ передачи результата в науку: идею, полученную с помощью внутренней модели, оформили в препринт внешние исследователи, а модель затем использовали для формальной проверки. Такая схема делает вопрос авторства и ответственности особенно конкретным.
Первоисточники и подтверждения
TelegramПодборку проверяет редакция DSML. AI помогает дедуплицировать сигналы и готовить текст, но опубликованный выпуск остаётся редакционным продуктом, а не лентой отдельных каналов.