ПРЕДЕЛ СКОРОСТИ ПОИСКА КЛИК ПАЛ СПУСТЯ 40 ЛЕТ
Представьте социальную сеть из n человек. Есть ли среди них группа из k человек, которые все знакомы друг с другом? Специалисты по информатике называют такую группу k-кликой, и её поиск — классическая задача с бесчисленными приложениями. Наивный подход перебирает все возможные группы из k человек — их примерно n^k, — что безнадёжно для больших сетей.
Приём 1985 года и давний вызов
Более 40 лет назад Ярослав Нешетржил (Jaroslav Nešetřil) и Сватоплук Поляк (Svatopluk Poljak) нашли обходной путь. Они свели поиск k-клики к поиску треугольника в графе побольше, а это, в свою очередь, можно сделать с помощью перемножения матриц — больших таблиц чисел. Затраты зависят от ω, показателя степени матричного умножения: их метод требует примерно n^(ωk/3) шагов. Точного значения ω никто не знает. Оно не меньше 2, а в статье приводится недавняя верхняя оценка 9/4.
Показатель степени этого метода 1985 года так никто и не превзошёл. В 2004 году прозвучал вызов Герхарда Вёгингера (Gerhard Woeginger) исследователям: улучшить результат хотя бы для какого-нибудь фиксированного k; прошло больше двух десятилетий. Тем временем гипотеза о k-клике (k-Clique Hypothesis) — что n^(ωk/3), по сути, наилучшее возможное время — стала одной из основ «мелкозернистой сложности» (fine-grained complexity). Исследователи опирались на неё, чтобы обосновать, что многие другие задачи, от синтаксического анализа по грамматикам до анализа сжатых данных, тоже нельзя решить быстрее.
Движущаяся мишень
У опровержения этой гипотезы была особая трудность. Предсказываемые ею затраты зависят от ω, а оно неизвестно. Алгоритм, который выигрывает у оценки с нынешним лучшим значением ω, мог бы перестать выигрывать у гипотезы, если бы кто-нибудь позже нашёл более быстрый способ перемножать матрицы.
Вирджиния Василевска Уильямс (Virginia Vassilevska Williams) из MIT и Ор Замир (Or Zamir) из Тель-Авивского университета обходят эту проблему. Они доказывают, что для любого достаточно большого k можно найти k-клику — и даже подсчитать число таких клик — примерно за n^((ω/3 − c)k) шагов, где c — положительная константа, не зависящая ни от k, ни от ω. Выигрыш отсчитывается от истинного значения ω, каким бы оно ни оказалось. Он сохраняется даже при ω = 2, в наилучшем мыслимом случае.
Складывая вилку
Сердце метода — работа с шаблонами из девяти вершин. Стандартный подход разбивает их на три группы по три и перемножает три огромные матрицы. Авторы рассматривают вилку (wedge) — два ребра с общей вершиной — и вставляют между двумя из матриц таблицу, которая ничего не меняет: единичную матрицу. Затем они записывают эту единичную матрицу как сумму нескольких «обменов» (swaps), каждый из которых сливает два ребра вилки в одно, плюс остаток малого ранга.
Обмены дают более простые шаблоны с меньшим числом рёбер, которые обрабатываются тем же методом заново; у шаблона из девяти вершин не больше 36 рёбер, так что рекурсия заканчивается. Остаток малого ранга уменьшает матрицы, которые нужно перемножать. Именно применение приёма сразу к двум отдельным вилкам позволяет сохранить выигрыш даже при ω = 2. Тогда любое k, кратное девяти, можно сгруппировать в девять блоков.
Реальный, но крошечный
Авторы не приводят численных значений выигрыша. Они описывают константы как лежащие «между мизерными без оптимизации и крошечными при значительной оптимизации». Суть не в практической скорости, а в том, что барьера, в который верили десятилетиями, не существует.
Последствия выходят за рамки клик. Точные алгоритмы для трудных задач оптимизации, таких как Max-Cut и Max-2-SAT, которые работали примерно за 2^(ωn/3) шагов для n переменных, теперь тоже получают меньший показатель степени. То же относится к подсчёту копий любого фиксированного небольшого графа.
Что сделал ИИ
В отдельном разделе авторы описывают, как работали с ChatGPT-6, которым пользовались через его общедоступный веб-интерфейс. Отталкиваясь от собственных идей авторов для клик из пяти человек и от недавнего результата OpenAI, опровергшего другую гипотезу — гипотезу экспоненциального времени (Exponential Time Hypothesis), — модель нашла первое, сложное улучшение для 5-клик. Затем авторы с помощью ИИ выделили из него алгебраическое разложение, лежащее в основе доказательства; это разложение они считают «почти исключительно вкладом ИИ». Построенный вокруг него алгоритмический каркас, по их словам, в основном принадлежит им.
Одно замечание выделяется особо. Непонятные доказательства, созданные ИИ, людям трудно читать, отмечают авторы, — и они «были впечатлены тем, что их трудно понять и самому ИИ».
