ИИ преодолевает пределы теории Рамсея с помощью AlphaEvolve

Исследователи достигли значительного прорыва в области **теории Рамсея**, использовав **AlphaEvolve** — новый металгоритм на базе больших языковых моделей (LLM) — для обнаружения новых нижних границ пяти классических чисел Рамсея. Увеличив известные нижние границы для **R(3, 13)**, **R(3, 18)**, **R(4, 13)**, **R(4, 14)** и **R(4, 15)**, исследовательская группа, в которую вошли **Prabhakar Raghavan**, **Ansh Nagda** и **Abhradeep Thakurta**, продемонстрировала, что ИИ способен решать сложные комбинаторные задачи, прогресс в которых отсутствовал десятилетиями. Эти результаты знаменуют переход от поисковых эвристик, созданных человеком, к оптимизации, разработанной машиной, предлагая новый путь для изучения фундаментальных границ порядка и хаоса в математических структурах.

Что такое числа Рамсея и почему их так сложно вычислить?

**Числа Рамсея**, обозначаемые как R(m, n), представляют собой наименьшее количество вершин в полном графе, при котором любая красно-синяя раскраска ребер обязательно должна содержать либо красную клику размера m, либо синюю клику размера n. Их общеизвестно трудно вычислить, так как количество возможных раскрасок графа растет экспоненциально с увеличением m и n, быстро превосходя вычислительные мощности даже самых мощных суперкомпьютеров в мире.

**Теория Рамсея**, которую часто объясняют через аналогию с «задачей о вечеринке», стремится найти минимальное количество гостей на встрече, необходимое для того, чтобы определенное число людей либо все знали друг друга, либо все были совершенно незнакомы. Хотя концепция проста — например, R(3, 3) равно 6 — сложность возрастает настолько стремительно, что точное значение R(5, 5) до сих пор неизвестно. Легендарный математик **Paul Erdős** однажды заметил, что если бы превосходящая инопланетная сила потребовала от нас вычислить R(5, 5) под угрозой уничтожения, человечество должно было бы направить все свои ресурсы на эту задачу; однако, если бы они спросили R(6, 6), нам следовало бы вместо этого готовиться к битве, так как вычисление, скорее всего, невозможно.

Сложность заключается в «центре хаоса», где математики пытаются определить первое появление порядка. Поскольку не существует известной формулы для прямого определения чисел Рамсея, исследователи полагаются на поиск «нижних границ» — наибольшего известного размера графа, который еще **не** содержит требуемых монохроматических клик. Исторически эти границы обнаруживались с помощью узкоспециализированных, разовых алгоритмов, разработанных специально для одного числа Рамсея, что делало процесс фрагментированным и трудновоспроизводимым для других математических случаев.

Как AlphaEvolve использует LLM для мутации кода математических доказательств?

**AlphaEvolve** функционирует как сложный агент мутации кода, который использует **большие языковые модели** для итеративного совершенствования алгоритмов поиска, а не просто для генерации статических решений. Рассматривая поиск комбинаторных структур как эволюционный процесс, система позволяет LLM выступать в роли «инженера», который модифицирует собственный код, чтобы лучше ориентироваться в обширном и сложном ландшафте **теории Рамсея**.

В отличие от традиционных приложений ИИ, действующих как разговорные чат-боты, AlphaEvolve работает как металгоритм. Процесс начинается с базовой структуры поиска, которую LLM затем «мутирует», предлагая архитектурные изменения, различные эвристические подходы или стратегии оптимизации. Эти мутации тестируются на соответствие математическим ограничениям задачи Рамсея. Успешные вариации — те, что находят более крупные графы без клик — закрепляются и используются в качестве основы для дальнейших мутаций. Это создает петлю обратной связи, в которой ИИ не просто ищет граф, а вырабатывает наиболее эффективный способ поиска этого графа.

Методология, примененная **Prabhakar Raghavan** и его коллегами, представляет собой отход от «ручных» эвристик, которые доминировали в этой области на протяжении многих лет. Вместо того чтобы математик-человек тратил месяцы на доработку конкретного алгоритма поиска для R(4, 13), AlphaEvolve автоматизирует этот процесс открытия. Этот металгоритмический подход достаточно универсален, чтобы применяться к различным числам Рамсея одновременно, доказывая, что одна система на базе ИИ может заменить десятки специализированных инструментов, написанных человеком.

Каковы новые нижние границы для R(3,13) и R(4,15)?

Новые нижние границы, обнаруженные AlphaEvolve для **R(3, 13)** и **R(4, 15)**, составляют **61** и **159** соответственно, что фактически побило рекорды, которые держались в течение значительного времени. Эти результаты представляют собой наименьший известный размер графа, в котором можно избежать специфических условий Рамсея, сужая диапазон поиска для математиков, пытающихся найти точные значения этих чисел.

Исследование успешно обновило пять классических чисел Рамсея со следующими улучшенными нижними границами:

• **R(3, 13):** Увеличено с 60 до **61**
• **R(3, 18):** Увеличено с 99 до **100**
• **R(4, 13):** Увеличено с 138 до **139**
• **R(4, 14):** Увеличено с 147 до **148**
• **R(4, 15):** Увеличено с 158 до **159**

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

Эволюция математических открытий

Это исследование знаменует собой поворотный момент в применении **больших языковых моделей** в точных науках. Хотя LLM часто критикуют за склонность к «галлюцинациям» в творческом письме, их полезность в генерации и мутации кода позволяет проводить строгую проверку. В контексте **теории Рамсея** каждый результат, полученный AlphaEvolve, математически проверяем: граф либо содержит определенную клику, либо нет. Эта объективная истина позволяет ИИ быстро совершать ошибки и учиться на них, превращаясь из творческого движка в высокоточный инструмент для математических доказательств.

Сотрудничество между исследовательской группой и агентом на базе LLM преодолевает критический разрыв между чистой математикой и обучением с подкреплением. Используя **AlphaEvolve**, **Prabhakar Raghavan** и его команда добились прогресса в задачах, которые ранее считались требующими человеческой интуиции или крайне специализированных вычислительных знаний. Способность металгоритма «соответствовать историческим эталонам и превосходить их» предполагает, что мы вступаем в эру, когда ИИ может обнаруживать закономерности и структуры, слишком сложные для идентификации с помощью стратегий поиска под руководством человека.

Будущие перспективы и следующие шаги

Успех AlphaEvolve в **теории Рамсея** открывает двери для его применения в других нерешенных задачах комбинаторики и теории графов. Поскольку система является металгоритмом, она не ограничивается числами Рамсея. Исследователи предполагают, что ее можно адаптировать для поиска экстремальных графов по другим свойствам, оптимизации сетевых топологий или даже помощи в открытии новых кодов, исправляющих ошибки, в теории информации.

По мере того как «эволюционный» аспект агента будет совершенствоваться, мы сможем увидеть еще более существенные скачки нижних границ. Исследователи отметили, что хотя нынешние улучшения являются постепенными (увеличение границ на 1), эти шаги имеют решающее значение для окончательного определения точных значений. Будущие итерации **AlphaEvolve** могут включать в себя более продвинутые способности к рассуждению, позволяя ИИ не только мутировать код поиска, но и выдвигать гипотезы о новых математических свойствах, которые могли бы еще больше сузить пространство поиска. На данный момент у комбинаторики появился мощный новый союзник в стремлении найти порядок в бесконечной сложности графов.