AlphaEvolve от Google DeepMind открыла новые нижние оценки для чисел Рамсея, улучшив результаты, которые не обновлялись десятилетиями

Числа Рамсея – это фундаментальные объекты в комбинаторной математике. Формально, число Рамсея R(s,t) – это минимальное число вершин в полном графе, при котором любое окрашивание ребер в два цвета (скажем, красный и синий) создает либо полносвязный подграф на s вершинах, где все ребра красные, либо полносвязный подграф на t вершинах, где все ребра синие.

Эта задача крайне вычислительно сложна. Даже для небольших значений типа R(5,5) точное значение неизвестно спустя почти век исследований, потому что для вычисления требуется перебор экспоненциального числа раскрасок графов. Это делает задачу неразрешимой даже на современных суперкомпьютерах.

Эрдеш, тот самый легендарный комбинаторщик, говорил, что R(5,5) посчитают только инопланетяне или следующая цивилизация.

Короче, числа Рамсея действительно очень сложны. А вчера DeepMind вдруг объявили, что AlphaEvolve самостоятельно воспроизвела все известные точные границы и улучшила значения для пяти классических случаев.

Особенно поражает, что исторически для приближения чисел Рамсея использовались только хитрые ручные алгоритмы, а тут пробить SOTA смогла +-универсальная система на основе LLM.

Статья