Google DeepMind представила Alphaevolve, систему, которая использует большие языковые модели для обнаружения и проверки новых комбинаторных структур. Эти структуры могут способствовать развитию исследований в области теоретической компьютерной науки, особенно в сложности приблизительного расчета.
Исследователи отмечают, что современные крупные языковые модели уже показали значительные результаты в математике и программировании, но до сих пор были плохими в обнаружении новых теорем. Основная проблема здесь — абсолютная правильность, которая имеет важное значение для математики. Любая претензия должна быть формально доказана или проверена экспертом.
В статье «Усиленная генерация комбинаторных структур: применение к теории сложности» (Интенсивное генерация комбинаторных структур: применение к теории сложности) Авторы описывают, как AlphaEvolve помогает обнаружить новые структуры, которые затем автоматически проверяются компьютером. Система работает по принципу эволюции: она генерирует много фрагментов программирования, выбирает наиболее успешные и постепенно уточняет их.
Этот подход позволил прогресс в двух направлениях в задаче MAX-4-Cut и в изучении свойств случайных столбцов.
Для задачи MAX-4-CUT до сих пор известно, что она не может быть лучше составлена, чем фактор 0,9883. Alphaevolve обнаружила новый так называемый «гаджет» — специальную конструкцию с 19 переменной и сложной системой веса. Это улучшило результат до 0,987. В области теории привязанности такие шаги считаются значительным достижением, поскольку любой новый барьер трудно преодолеть.
Кроме того, система исследует среднюю сложность задач на случайных столбцах, где столбцы Рамануджана играют ключевую роль. Alphaevolve удалось найти такие колонны для сотен пиков — гораздо больше, чем он мог сделать раньше. Это помогло уточнить пределы вычисления сложности и почти полностью провести практически нижние и верхние оценки.
Основная особенность работы заключается в том, что все найденные структуры были проверены на правилу не только ускоренными методами, но и с помощью исходного «грубого» алгоритма. Это гарантирует надежность результатов.
Авторы подчеркивают, что это еще не является способностью доказать новые теоремы самостоятельно, но теперь такие системы могут создавать элементы доказательств, которые затем «подняты» в более общих универсальных результатах. В будущем ключевой проблемой будет проверять точность, поскольку объем расчетов для этой цели будет расти со сложностью задач.
