Claude Opus 4.6 решил задачу Кнута о гамильтоновых циклах в ориентированных графах
Искусственный интеллект Claude Opus 4.6 справился с задачей, над которой трудился сам Дональд Кнут — легендарный учёный и автор фундаментального труда The Art of Computer Programming. Проблема касается разбиения рёбер ориентированного графа на три направленных гамильтоновых цикла, проходящих через все вершины ровно по одному разу. До недавнего времени решение можно было найти лишь для частных случаев.
Задача сформулирована следующим образом: вершинами графа являются все тройки целых чисел (i, j, k) в диапазоне от 0 до m−1. Из каждой вершины исходят три дуги — для увеличения i, j или k по модулю m. Необходимо разбить все дуги на три гамильтоновых цикла, покрывающих все вершины, для любого m > 2. Кнут с коллегами сумели доказать это лишь для m = 3; эмпирические исследования нашли решения для небольших m вплоть до 16.
Claude Opus 4.6 — ИИ, разработанный для решения сложных вычислительных и комбинаторных задач — после часа вычислений вывел конструкцию, которая работает для всех нечётных значений m. Этот результат не только расширяет границы известного, но и ставит новые стандарты в области применения генеративного искусственного интеллекта в математике.
Почему решение «Claude’s Cycles» важно для математики и ИИ
Задача с ориентированным графом является классической в теории графов и комбинаторике, а её сложности связаны с управлением огромным числом вершин — объём графа растёт как m³. Ручное или эмпирическое решение ограничено малыми m, что мешало выстроить общую теорию. Использование ИИ позволило отказаться от рутинных переборов и найти общий алгоритм для нечётных m.
Такой успех делает ИИ не просто инструментом вычислений, а партнёром в поиске новых математических идей. Отметим, что Кнут, признанный властелин алгоритмов, не скрывает удивления и уважения к решению Claude Opus 4.6. Название «Claude’s Cycles» стало новичком в математической литературе и, возможно, началом новой эры совместных исследований человека и ИИ.
Контекст и перспективы: куда ведут успехи ИИ в теории графов
Использование генеративного ИИ в чистой математике — пока редкость. В числе известных аналогов — достижения ИИ в доказательствах теорем или поиске контрпримеров. Однако Claude Opus 4.6 переходит от частных к общим конструкциям, что по-настоящему меняет правила игры.
Подобные достижения стимулируют развитие гибридных подходов, где человек формулирует задачу и интерпретирует результат, а ИИ берёт на себя тяжёлый поиск новых способов решения. Можно ожидать, что в ближайшие годы подобные инструменты ускорят прогресс в других областях, включая топологию, теорию чисел и оптимизацию.
Вопрос остаётся открытым: смогут ли ИИ и математики совместно решить нечётные, а затем и чётные значения m, или потребуются новые идеи и методы? Claude’s Cycles — первая ступень на пути к более глубокому взаимопониманию и сотрудничеству, где интеллект машины дополняет и расширяет творческий потенциал человека.
