- Модель ИИ Claude Opus 4.6 за один час решила сложную задачу из теории графов, над которой Дональд Кнут трудился неделями.
- Задача связана с разложением дуг ориентированного графа на три гамильтоновых цикла для графов размером m³, причем модель нашла конструктивное решение для всех нечетных m от 3 до 101.
- Кнут предоставил строгое математическое доказательство построенного ИИ решения, признал масштабный прорыв в генеративном ИИ, но вопрос для четных m остался открытым.
Легендарный информатик Дональд Кнут, известный как автор фундаментального труда The Art of Computer Programming и лауреат премии Тьюринга, опубликовал на сайте Стэнфордского университета статью под заголовком «Claude’s Cycles», в которой поделился поразительным опытом взаимодействия с искусственным интеллектом Claude Opus 4.6 от компании Anthropic. Модель ИИ всего за час смогла найти решение сложной задачи из теории графов, которая ранее занимала Кнута и его коллег несколько недель.
Суть задачи состоит в разложении дуг ориентированного графа с m³ вершинами — каждая вершина кодирует тройку чисел (i, j, k), причем из каждой вершины выходит три дуги, ведущих к увеличению каждой координаты по модулю m. Требовалось разработать универсальную конструкцию разложения дуг на три гамильтоновых цикла, которая была бы справедлива для любого m>2. Сам Кнут смог решить только частный случай при m=3, а его коллега Филип Стапперс эмпирически подобрал решения для m от 4 до 16, при этом общий закономерный алгоритм оставался неуловим.
Стапперс решил обратиться к модели Claude Opus 4.6, предоставив ей точное математическое описание задачи. В результате за 31 итерацию и около часа работы модель эволюционировала от простого перебора до более глубокого анализа структуры графа с применением метода разложения по слоям (fiber decomposition), в итоге разработав конкретную конструкцию, реализованную программно на Python. Полученное решение подтвердилось корректным для всех нечетных m в диапазоне от 3 до 101.
Важный момент: решение носит конструктивный характер, но математического доказательства его универсальной корректности для всех нечетных m не было. Это доказательство впоследствии условно предоставил лично Кнут, подтвердив, что найденная конструкция — лишь одна из 760 возможных вариантов, которые «похожи на Claude» и пригодны для нечетных параметров.
Процесс совместной работы с ИИ оказался непростым: Стапперс вынужден был периодически перезапускать сеансы из-за сбоев, модель иногда забывала документировать промежуточные результаты. При этом задача для четных значений m остается неразрешённой: Claude Opus 4.6 выдвигал гипотезы, однако обобщённого решения не представил.
Впечатлённый успешным применением современных генеративных ИИ, сам Дональд Кнут подчеркнул необходимость переосмысления взглядов на возможности таких систем в области автоматического доказательства и творческого решения сложных математических проблем. Он выразил радость не только в связи с подтверждением своей гипотезы, но и в аспекте достижения прорыва, продемонстрированного ИИ.
