В понедельник 5-го октября на архив выложили препринт «Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs». В нём опровергают две гипотезы о сложности алгоритмов решения двух задач. Одна из них формулируется очень просто, и вы наверняка на неё натыкались, если готовились к собеседованиям на LeetCode — 3 sum. Вам дан массив из n чисел (включая отрицательные), и нужно определить, есть ли в нём 3 таких, что их сумма равна нулю.

В теоретической информатике долгое время существовало предположение, что для этой задачи невозможно найти алгоритм, который работал бы существенно быстрее квадратичного от размера массива. 3 sum — одна из центральных гипотез раздела fine-grained complexity. Многие другие задачи можно свести к 3 sum. Поэтому на предположении строилось множество других результатов: исследователи показывали, что если 3 sum невозможно существенно ускорить, то нельзя существенно ускорить и целый ряд других задач.

И вот оказалось, что существует общий алгоритм, который вместо n^2 работает за n^(1.9992). Само по себе ускорение не особо интересно (в практике оно может работать даже медленнее, так как из нотации выкидывают константы) — и ключевым является именно опровержение гипотезы, которыми многими считалось «логичной» и «красивой».

Один из двух авторов — Virginia Vassilevska Williams, одно из ведущих имён в области fine-grained complexity. И казалось бы можно порадоваться за прорыв, но если открыть конец статьи, то увидим:

Как результат был первоначально получен и передан авторам: сотрудник Anthropic использовал внутреннюю исследовательскую модель для изучения открытых проблем в теории криптографии. <...> В сентябре 2026 года Anthropic передала алгоритм авторам на условиях соглашения о конфиденциальности, предложила вознаграждение и предоставила доступ к публичной версии Claude.
<...> После того как статья была полностью написана, Anthropic использовала внутреннюю исследовательскую модель для формальной проверки основных результатов статьи с помощью Lean. <...> Авторы работали над этой публикацией в личное время, вне рамок своих служебных обязанностей в Колумбийском университете и MIT.
Так что получился немного странный для науки подход «найти и проспонсировать подставное лицо, не участвовавшее в составлении доказательства, и указать его в качестве автора, и при этом указать, что работает он без своей основной аффилиации».

Я против такого подхода ничего не имею, но многие в научном сообществе видят здесь несоответствие... духу? морали? науки и тому, как вещи «принято» делать. Но в конечном итоге есть ведущий учёный, который вчитался в результат, проверил, поставил своё имя под ним, что даёт хоть какую-то гарантию легитимности, и есть надежда, что результат будет использоваться в будущих исследованиях.