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

Сейчас легендарному Дональну Кнуту 88 лет, но он продолжает работать и даже писать. Конкретно сейчас он занят написанием четвертого тома The Art of Computer Programming (а именно, третьей его части). Этот том полностью посвящен комбинаторным задачам.

И вот вчера, внезапно, на сайте Стэнфорда появляется статья его авторства, которая начинается буквально со слов "ШОК! ШОК!".

Оказалось, что Claude Opus 4.6 решил сложную задачу, над которой сам Кнут и его друзья работали неделями. Задача связана с поиском гамильтоновых циклов. Формулировка для тех, кому интересно:

Рассматривается ориентированный граф, вершинами которого являются все возможные тройки целых чисел i, j и k от 0 до m−1. Из каждой вершины выходят три дуги: одна ведет в вершину, где увеличивается i на единицу по модулю m, вторая – где увеличивается j на единицу по модулю m, и третья – где увеличивается k на единицу по модулю m. Всего в таком графе m³ вершин и у каждой вершины по три исходящих дуги. Требуется найти общий способ, который для любого m больше 2 разбивает все дуги этого графа на три направленных цикла, причtм каждый из них должен проходить через все вершины ровно один раз, то есть быть гамильтоновым циклом.

Она возникла как раз во время написания новой книги. Сам Кнут работал над ней несколько недель, но нашел решение только для случая m = 3. Его коллега Filip Stappers затем попробовал исследовать задачу вычислительно и эмпирически нашел разложения для m от 4 до 16.

Решение в общем виде никому из них найти не удалось, пока Stappers не задал задачу Claude Opus 4.6. Бот думал примерно час и нашел конструкцию, которая работает для всех нечетных m.

С подачи Кнута задача получила название "Claude’s Cycles", и вот что он пишет об этом результате:

"Похоже, мне придется пересмотреть свои взгляды на генеративный ИИ. <> Подход Claude к решению был очень впечатляющим. <> Думаю, дух Клода Шеннона гордится, что его имя теперь связано с такими прорывами. Браво, Клод!"

cs.stanford.edu/~knuth/papers/claude-cycles.pdf