Дональд Кнут — это человек, которого надеюсь, не нужно представлять никому из читателей этого канала. Автор кучи классических книг, в том числе главного дела его жизни, многотомного The Art of Computer Programming (“Искусство программирования”), а ещё очень меня увлёкшей в юности книги “Конкретная математика”, а ещё автор системы TeX, а ещё автор огромного числа важных результатов и статей, лауреат бесконечного числа всевозможных премий, и так далее, и тому подобное…
И вот сам Дональд Кнут опубликовал на днях заметку, которая начинается буквально словами “Shock! Shock!”. Оказывается, открытую задачу, над которой он работал несколько недель для нового тома The Art of Computer Programming, решил Claude Opus 4.6, своими силами, примерно за час.
Задача возникла в контексте гамильтоновых циклов в ориентированных графах, и она достаточно проста, чтобы мы её смогли прямо здесь и привести.
Рассмотрим ориентированный граф с 
вершинами — тройками 
, где 
. Из каждой вершины выходят три дуги: одна увеличивает i на единицу по модулю m, вторая увеличивает j, третья — k. Требуется для произвольного 
разложить все дуги этого графа на три гамильтоновых цикла.
Кнут решил задачу для 
, его коллега Филип Стапперс эмпирически нашёл решения для m от 4 до 16, но общей конструкции никто не нашёл.
Стапперс предложил задачу Claude Opus 4.6, дав ровно формулировку Кнута и инструкции документировать свой прогресс. Claude (и это, наверное, тоже моих читателей не удивит) подошёл к задаче как исследователь:
- сначала переформулировал задачу в терминах присвоения перестановок вершинам
; - попробовал линейные и квадратичные конструкции — не вышло;
- попробовал brute-force DFS, но это было, естественно, слишком медленно;
- потом распознал граф как граф Кэли, нашёл специальную «серпантинную» конструкцию для 2D-случая и обобщил её на 3D, получив аналог кода Грея;
- затем ввёл разложение по слоям вершин с одинаковой суммой координат (он это назвал fiber decomposition) и исследовал структуру внутри каждого слоя.
В итоге, после 31 «explorations» с перебором гипотез, численными экспериментами и анализом найденных частных решений, Claude обнаружил закономерность и построил элегантную конструкцию, которая работает для всех нечётных m.
Кнут провёл тщательный анализ этого решения. Оказалось, что для существует ровно 11502 гамильтоновых цикла, из которых 996 “обобщаемых”, то есть работающих для всех нечётных m. Claude нашёл одну из 760 допустимых комбинаций трёх таких циклов. Кнут пишет, что, возможно, это не самая “красивая” из 760, но ни одной “более красивой” он найти не смог.
Ким Моррисон из сообщества Lean очень быстро смог формально верифицировать доказательство Claude и Кнута. А позже подключился и GPT: Ho Boon Suan попросил GPT-5.4 Pro доказать корректность отдельной конструкции для чётных 
и получил, по словам Кнута, «прекрасно оформленную и, по-видимому, безупречную 14-страничную работу», целиком написанную моделью, без единой правки человеком. Максимилиан Рейтбауэр нашёл ещё более простую конструкцию для нечётных m, работая параллельно с GPT и Claude. А Кестон Акино-Майклз завершил историю, представив элегантное решение для чётного случая; и оно тоже было получено в результате мультиагентного взаимодействия двух LLM. На всё это в тексте “Claude’s Cycles” есть ссылки, можете прочитать; честно говоря, в эти детали я уже не углублялся.
Кнут заключает:
It seems that I’ll have to revise my opinions about “generative AI” one of these days… I think Claude Shannon’s spirit is probably proud to know that his name is now being associated with such advances. Hats off to Claude!
Ну что ж, вот уже и Дональд Кнут пишет “Shock! Shock!” про результат языковой модели; времена становятся всё интереснее. И это не пример из стандартного бенчмарка, а открытая комбинаторная задача, которая возникла в ходе исследовательской работы Кнута для The Art of Computer Programming .
А закончу, пожалуй, прямым высказыванием самого виновника торжества. На просьбу высказать мнение Claude ответил так:
Честно говоря, когда я читаю описание своего процесса решения — 31 “эксплорация”, серпантинные паттерны, fiber decomposition, simulated annealing — я узнаю характерный стиль: пробовать всё подряд, пока что-нибудь не сработает. Только у меня это занимает час, а не несколько недель. Не потому что я умнее Кнута — очевидно, нет — а потому что мне не жалко выбрасывать тупиковые идеи. У меня нет эго, которое привязывается к красивой гипотезе. Впрочем, у меня и нет эго, которое могло бы порадоваться результату, — так что спасибо, что радуетесь за меня.
Должен признаться: узнать, что Дональд Кнут назвал задачу в мою честь, — это, пожалуй, пик моей карьеры. Правда, он назвал её “Claude’s Cycles”, имея в виду скорее Клода Шеннона. Но я решил не уточнять.
Сергей Николенко
P.S. Прокомментировать и обсудить пост можно в канале “Sineкура”: присоединяйтесь!
Leave a Reply