Claude Opus 4.6 за час решил задачу, над которой Дональд Кнут бился неделями

88-летний Дональд Кнут — легендарный информатик, лауреат премии Тьюринга и автор The Art of Computer Programming — опубликовал на сайте Стэнфорда статью с заголовком "Claude's Cycles". Она начинается со слов "ШОК! ШОК!": оказалось, что модель Claude Opus 4.6 от Anthropic решила открытую задачу из теории графов, над которой Кнут работал несколько недель.

Задача возникла при написании нового тома The Art of Computer Programming и связана с разложением дуг ориентированного графа на три гамильтоновых цикла. Граф имеет 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.

Процесс не был гладким: Стапперсу приходилось перезапускать сессии из-за ошибок, а модель периодически забывала документировать свой прогресс. Задача для четных m