- Claude Opus 4.6 d’Anthropic a résolu le problème de décomposition en cycles hamiltoniens orientés sur lequel Donald Knuth travaillait depuis plusieurs semaines
- Le problème consiste à trouver une décomposition en trois cycles hamiltoniens d’un graphe orienté ayant (m^3) sommets, et Claude l’a résolu de manière complète pour les m impairs
- Claude a procédé par étapes en combinant diverses stratégies d’exploration, notamment la décomposition en fibres, des motifs serpentin 3D, la recherche en profondeur (DFS) et le recuit simulé
- Il a finalement dérivé une solution générale sous la forme d’un programme Python, que Filip Stappers a vérifiée pour les m impairs de 3 à 101, confirmant une décomposition complète
- Knuth considère ce résultat comme une avancée majeure du raisonnement automatisé et de la résolution créative de problèmes, tout en précisant que le cas des m pairs reste non résolu
Contexte et définition du problème
- Le sujet de recherche porte sur les cycles hamiltoniens orientés et doit figurer dans un futur volume de The Art of Computer Programming de Knuth
- Le graphe est composé de (m^3) sommets (ijk), avec trois arêtes sortantes depuis chaque sommet : (i+jk), (ij+k), (ijk+)
- L’objectif est de trouver, pour tout (m>2), une solution générale permettant de décomposer ces arêtes en trois cycles orientés de longueur (m^3)
Processus d’exploration de Claude
- Claude Opus 4.6 est le modèle de raisonnement hybride d’Anthropic ; Filip Stappers lui a soumis le problème et lui a demandé de documenter son cheminement
- Dans un premier temps, Claude a reformulé le problème comme un graphe fonctionnel et un problème d’affectation de permutations, puis a tenté des approches linéaires et quadratiques sans succès
- Il a ensuite expérimenté successivement une exploration DFS, l’analyse de motifs serpentins 2D et des motifs fondés sur le code Gray en 3D
- En introduisant l’approche de décomposition en fibres, il a analysé une structure stratifiée selon (s = (i+j+k) \mod m) et découvert des solutions partielles via le recuit simulé (SA)
Découverte et vérification de la solution
- À l’étape 31 de l’exploration, Claude a généré un programme Python fondé sur une règle dépendant d’une seule coordonnée par fibre
- Ce programme produit trois cycles hamiltoniens complets pour m=3,5,7,9,11
- Filip Stappers l’a ensuite testé pour tous les m impairs de 3 à 101, confirmant une décomposition complète
- Knuth l’a simplifié en code C, puis a démontré mathématiquement que chaque cycle est bien de longueur (m^3)
Généralisation et analyse mathématique
- Il a été confirmé que certains cycles hamiltoniens pour (m=3) peuvent être généralisés à tous les m impairs
- Parmi les 11 502 cycles pour (m=3), 1 012 se généralisent à (m=5), et 996 jusqu’à (m=7)
- Ces 996 cycles sont généralisables à tout m impair > 1
- Une décomposition de type « Claude-like » est définie par des règles simples ne dépendant que des valeurs limites de i, j et s (0 ou m−1)
- Théorème : pour qu’une décomposition « Claude-like » soit valide pour tout m impair > 1, les trois cycles pour m=3 doivent être des cycles hamiltoniens généralisables
- Les calculs montrent que 760 décompositions « Claude-like » sont valides pour tous les m impairs
Cas non résolu des m pairs et conclusion
- Le cas des m pairs reste ouvert
- L’impossibilité pour (m=2) a déjà été démontrée dans des travaux antérieurs
- Claude a trouvé des solutions partielles pour (m=4,6,8), sans parvenir à les généraliser
- Lors de l’exploration du cas pair, Claude a montré des erreurs et des comportements anormaux, ce qui a conduit à l’arrêt de la recherche
- Knuth y voit une réalisation historique du raisonnement automatisé fondé sur l’IA, et une avancée digne du nom de Claude Shannon
Annexe : règles des deux autres cycles
- Deuxième cycle (c=1) :
- si (s=0), alors j augmente ; si (0<s<m−1), alors i augmente ; si (s=m−1), alors si i>0, k augmente, et si i=0, j augmente
- Troisième cycle (c=2) :
- pour (s=0), si j<m−1, alors i augmente, et si j=m−1, alors k augmente
- pour (0<s<m−1), si i<m−1, alors k augmente, et si i=m−1, alors j augmente
- si (s=m−1), alors i augmente
- L’ordre des sommets pour s=0 dans chaque cycle est explicitement donné, ce qui permet de démontrer la structure de l’ensemble des cycles
Aucun commentaire pour le moment.