Исследователи из Google и Google DeepMind опубликовали работу, в которой с помощью AlphaEvolve улучшили нижние границы для пяти классических чисел Рамсея — R(3,13), R(3,18), R(4,13), R(4,14) и R(4,15). Каждая из границ выросла на единицу, но в теории Рамсея, где прогресс измеряется десятилетиями, это заметный результат: предыдущий рекорд для R(3,18) был установлен в 2006 году, для R(3,13), R(4,13) и R(4,14) — в 2015-м, для R(4,15) — в 2020-м.

Числа Рамсея — классическая задача комбинаторики: R(r,s) показывает, сколько вершин нужно графу, чтобы в нем гарантированно нашлась клика размера r или независимое множество размера s. Точные значения известны лишь для совсем маленьких параметров, а для остальных математики десятилетиями двигают нижние и верхние границы. Поль Эрдёш когда-то заметил: если инопланетяне потребуют вычислить R(5,5), человечеству стоит бросить на это все ресурсы, а вот для R(6,6) — лучше сразу атаковать инопланетян. Впрочем, сказано это было в 1990 году — и, как мы видим, возможности человечества выросли.

До сих пор каждый сдвиг нижней границы требовал узкоспециализированного алгоритма, заточенного под конкретную пару (r,s). Авторы пошли другим путем: AlphaEvolve использовался как единый метаалгоритм, который сам порождал поисковые процедуры для каждого случая. Система стартовала с пустого графа и эволюционно наращивала программы поиска, а не конструкции фиксированного размера. Обнаруженные алгоритмы разделились на четыре семейства — от случайной инициализации и алгебраических затравок (графы Пэли, кубические вычеты) до циклических конструкций и гибридных спектрально-фрактальных подходов.

Впрочем, сами по себе сдвиги на единицу — не главный результат работы. Числа Рамсея здесь скорее полигон: задача с четким критерием успеха, на которой удобно проверять возможности системы. Ключевое достижение в том, что один метаалгоритм заменил десятки узкоспециализированных программ, которые математики конструировали вручную годами. AlphaEvolve не просто решает задачу — он пишет программы, которые ее решают, причем найденные им процедуры существенно отличаются от предшественников: вместо стандартного имитационного отжига они комбинируют несколько эвристик, используют табу-поиск и собственные приближенные счетчики клик.

Теория Рамсея при этом не оторвана от практики — ее результаты применяются в теории кодирования, криптографии и анализе сетей. Но для Google DeepMind важнее другое: AlphaEvolve уже применялся к задачам от умножения матриц до проблемы Какеи в конечных полях, и каждый новый класс задач подтверждает универсальность подхода "ИИ ищет алгоритмы поиска".

P.S. Поддержать меня можно подпиской на канал "сбежавшая нейросеть", где я рассказываю про ИИ с творческой стороны.