Donald Knuth publie un article expliquant comment Claude Opus 4.6 a résolu un problème ouvert de combinatoire

Résumé essentiel

• Donald Knuth, informaticien et auteur de The Art of Computer Programming (TAOCP), a annoncé que le dernier modèle d’IA, Claude Opus 4.6, avait résolu un problème ouvert de combinatoire sur lequel il travaillait depuis plusieurs semaines.
• Sur un problème consistant à trouver une décomposition en cycles hamiltoniens d’un graphe orienté, Claude a découvert une structure d’algorithme généralisée et fonctionnelle au terme de 31 exécutions de scripts Python et d’une boucle d’auto-retour critique.
• Knuth, qui s’était montré sceptique par le passé en soulignant les limites de l’IA générative, a qualifié ce résultat de « progression spectaculaire en déduction automatique et en résolution créative de problèmes », laissant entendre qu’il réviserait son point de vue antérieur sur l’IA.

Analyse approfondie

Le problème résolu : décomposition en cycles hamiltoniens (Hamiltonian Cycle Decomposition)
Knuth étudiait un problème de décomposition sur certains graphes orientés (digraphs) tout en rédigeant le prochain volume de TAOCP. Dans un graphe comportant m^3 sommets ijk, avec 0 \le i, j, k < m, chaque sommet possède 3 arcs dirigés vers i+jk, ij+k, ijk+ (où i+ = (i+1) \bmod m). L’objectif était de trouver, pour tout m > 2, une solution générale (general decomposition) décomposant ces arcs en 3 cycles orientés de longueur m^3. Knuth avait résolu le cas m=3, mais peinait à en dériver une formule généralisée au-delà.

Principe d’implémentation et contexte technique : raisonnement hybride et boucle d’exploration autonome
Filip Stappers, un collègue de Knuth, a soumis ce problème au dernier modèle de raisonnement hybride d’Anthropic, Claude Opus 4.6. Au-delà d’une simple requête, le prompt imposait de fortes contraintes destinées à forcer un workflow agentique (Agentic).

Claude a immédiatement reformulé le problème d’un point de vue mathématique, puis a écrit des scripts Python (exploreXX.py) pour lancer une boucle de validation d’hypothèses. Pendant environ une heure, il a effectué 31 explorations en testant divers algorithmes, notamment la force brute (Brute force), les décompositions en fibres (fiber decompositions) et le recuit simulé (Simulated Annealing).

Le point de bascule décisif dans la résolution
Lors de la 25e exploration en particulier, Claude a analysé ses propres limites en notant que « l’algorithme de recuit simulé peut trouver des solutions individuelles, mais ne peut pas fournir une construction mathématique générale ; une approche purement mathématique est donc nécessaire », puis a réorienté sa recherche. Finalement, à la 31e exploration, il a dérivé une structure généralisée exacte, fonctionnant lorsque m est impair, en s’appuyant sur les motifs structurels identifiés au cours des explorations précédentes. Knuth a ensuite achevé la preuve mathématique à partir de ce résultat et a baptisé l’approche « décompositions de type Claude » (Claude-like decompositions).

Code et données principaux

Voici une partie des contraintes centrales (prompt) que Filip Stappers a imposées à Claude, ainsi que des extraits du journal d’auto-évaluation enregistré par Claude.

# 1. Contraintes de workflow imposées à Claude (contrôle de boucle et documentation obligatoire)  
"""  
After EVERY exploreXX.py run, IMMEDIATELY update this file [plan.md] before doing anything else.   
No exceptions. Do not start the next exploration until the previous one is documented here.  
"""  
  
# 2. Reformulation mathématique du problème par Claude (approche initiale)  
"""  
Need sigma: Z3 m — S3, assigning a permutation of {0,1,2} at each vertex;   
cycle c at vertex v goes in direction sigma(v)[c].   
Each resulting functional digraph must be a single Hamiltonian cycle.  
"""  
  
# 3. Auto-évaluation de Claude après la 25e exploration (changement d’orientation)  
"""  
SA(Simulated Annealing) can find solutions but cannot give a general construction.   
Need pure math.  
"""