Un problème ouvert a été soumis à Claude, avec l’espoir que cette IA aide à prouver la conjecture émise. Cette expérience est l’occasion d’évoquer la théorie de la résolution de problèmes, et surtout, de leur complexité.
On va donc commencer par donner quelques définitions sur lesquelles est basée la conjecture, puis de décrire le travail de recherche assistée lié à cette conjecture, après avoir énoncé celle-ci.
Les conversations avec une IA sont regroupées dans des fichiers pdf ; en dehors de cela, aucune IA n’a été utilisée pour rédiger l’article lui-même. L’article est sous licence CC-By-SA.
On commence donc par des définitions, pas nécessairement standard mais en cohérence avec la suite de l’article. Et, tout d’abord, puisqu’on cite de plus en plus le mot algorithmique, il est peut-être temps de définir ce mot, et avant tout, le mot algorithme.
C’est quoi un algorithme ?
Je propose la définition suivante, cohérente avec la suite de cet exposé :
Un algorithme est une suite d’instructions claires et non ambigües dont l’exécution permet en un temps fini et reproductible d’aboutir à la solution d’un problème.
Par reproductible j’entends que si Jean applique l’algorithme à un jeu de données puis que Jacques applique le même algorithme au même jeu de données, ils trouveront tous les deux la même solution au problème. Cela semble être en contradiction avec les algorithmes de Monte-Carlo et de Las Vegas, mais dans ces cas-là, les solutions trouvées sont des approximations de la même solution.
On remarque que, s’il n’y a pas de problème à résoudre, il n’y a pas d’algorithme. On est même en droit, en voyant un algorithme, de demander quel est le problème qu’il résout. Et la réponse le problème à résoudre est la programmation du programme de calcul en Scratch n’est pas une option valable pour moi : l’énoncé du problème précède systématiquement celui de l’algorithme, sinon on ne pratique pas une science, seulement de l’onanisme intellectuel...
On remarque également que, pour définir rigoureusement la notion d’algorithme, on doit d’abord définir la notion de problème :
C’est quoi, un problème ?
Pour Conway, un problème mathématique, c’était juste un jeu à un joueur (comme sudoku, solitaire, le jeu icosien ou celui de la camionneuse etc.). Pour la théorie de la complexité, la définition d’un problème est bien plus étonnante :
Un problème (de décision) est un langage, c’est-à-dire un ensemble de textes.
Tout d’abord, les problèmes dont la complexité est connue se ramènent à des problèmes de décision. Par exemple, la recherche du nombre chromatique d’un graphe, c’es-à-dire du nombre minimum de couleurs qu’il faut pour le colorier proprement, se ramène au problème de décision peut-on colorier ce graphe avec seulement trois couleurs ? et d’autres problèmes de décision obtenus en remplaçant trois par un autre nombre. Ainsi, lorsqu’on cherche à évaluer la complexité d’un jeu combinatoire, le problème de décision associé est existe-t-il une stratégie gagnante pour le joueur qui joue en premier ?.
Ensuite, un problème de décision équivaut à la description de ses solutions (les entrées pour lesquelles la réponse est oui) et lesdites solutions forment un langage formel. Ce point de vue est intéressant car il associe fortement la résolution de problèmes centrale aux mathématiques, avec la linguistique que l’on a en général plutôt tendance à dissocier de l’enseignement des mathématiques.
C’est quoi l’algorithmique ?
Contrairement à ce qu’on lit un peu partout, l’algorithmique est une science que l’on étudie souvent sans ordinateur. C’est la science des algorithmes, que l’on étudie et compare du point de vue de leur coût (en temps ou en espace) qui est la durée du calcul ou la place mémoire occupée pour résoudre une instance du problème, vu comme une fonction de la taille de l’instance. Par exemple, voici un problème célèbre :
énoncé
Ces deux nombres sont-ils premiers entre eux ?
Il s’agit d’un problème de décision, que l’on peut obtenir à partir du problème déterminer le pgcd de ces deux entiers. Le langage considéré est l’ensemble des couples (a,b) pour lesquels la fraction a/b est irréductible.
On connaît quatre algorithmes résolvant ce problème, que l’on comparera après les avoir décrits dans les onglets suivants.
définition
Pour savoir si deux entiers sont commensurables, on peut calculer leur pgcd puis le comparer avec 1. Pour calculer le pgcd de a et b, on peut utiliser l’algorithme (dit naïf parce qu’il découle directement de la définition) suivant :
- on calcule la liste des diviseurs de a (coût proportionnel à a),
- on calcule également la liste des diviseurs de b (coût proportionnel à b),
- on calcule l’intersection de ces deux listes (coût proportionnel à a×log(b) si les listes sont triées)
- on cherche le plus grand élément de l’intersection (coût constant : c’est le dernier élément de l’intersection)
- on compare le pgcd avec 1 (coût constant aussi).
L’algorithme « naïf » est donc de coût linéarithmique (proportionnel à n×log(n) si n est une mesure raisonnable de la taille des données d’entrées) en temps (et de coût linéaire en espace). Pas mal, mais ce n’est pas l’algorithme utilisé par Euclide dans son livre X. Pour savoir pourquoi, il reste à étudier le coût de ce dernier.
Le dixième livre
Dans le livre X de ses éléments, Euclide propose l’algorithme suivant, où a et b sont maintenant des variables, et consistant à répéter les opérations ci-dessous jusqu’à ce que a=b :
- on soustrait la plus petite des variables a et b, à la plus grande,
- on conserve la variable qui était la plus petite, et la différence.
Lorsque l’algorithme s’arrête, les valeurs initiales de a et b étaient premières entre elles, si et seulement si la valeur finale de a et b est égale à 1.
En considérant la recherche de minimum et la soustraction comme des opérations élémentaires, le coût de cet algorithme est le nombre de passages dans la boucle, c’est-à-dire le nombre de soustractions que l’on effectue. Le pire cas est celui où a et b sont des nombres de Fibonacci consécutifs, et le nombre de passages dans la boucle est le rang de b dans la suite de Fibonacci. L’algorithme a donc un coût proportionnel à log(a). Il est donc meilleur que l’algorithme « naïf » vu à l’onglet précédent.
Euclide
L’algorithme attribué à Euclide n’est pas celui du livre X, il en est une amélioration, où l’on répète jusqu’à ce que a=b les opérations suivantes :
- on divise a par b (division euclidienne évidemment !),
- on remplace simultanément a par b et b par le reste dans la division euclidienne.
Là encore, le coût est logarithmique (le pire cas reste celui où a et b sont des nombres de Fibonacci successifs), mais comme une division euclidienne résume des soustractions successives, l’algorithme improprement appelé « d’Euclide » teste plus vite la commensurabilité, que l’algorithme utilisé par Euclide. C’est donc l’algorithme le plus utilisé aujourd’hui (par exemple la fonction gcd de Python l’utilise).
facteurs premiers
Un autre algorithme possible pour tester la commensurabilité de deux nombres a et b est celui-ci :
- on décompose a en facteurs premiers (coût proportionnel à a),
- on décompose b en facteurs premiers (coût proportionnel à b),
- on regarde, pour chaque facteur premier commun à a et b, si son exposant vaut au moins 2 dans chacun des nombres a et b (coût proportionnel au nombre de facteurs premiers communs).
Le coût de cet algorithme est donc linéaire.
algorithmique
Voici le classement, par ordre croissant de coût en temps, des quatre algorithmes des onglets précédents :
- l’algorithme dit « d’Euclide »,
- l’algorithme utilisé par Euclide (soustractions successives),
- l’algorithme passant par la décomposition en facteurs premiers,
- l’algorithme « naïf » (dépendant de la définition).
Ce classement explique pourquoi, lorsqu’on doit tester la commensurabilité de deux entiers, on utilise en général l’algorithme dit « d’Euclide » : c’est le plus efficace des algorithmes connus.
On constate que le coût de tous ces algorithmes est majoré par un coût quadratique et on dit alors que le problème de test d’incommensurabilité est de complexité polynomiale (voir plus bas).
C’est à cela que sert l’algorithmique : en comparant les coûts de plusieurs algorithmes résolvant un même problème, elle aide la mathématicienne qui doit résoudre un problème, à prélever le meilleur outil dans la boîte à outils.
Comment évaluer la complexité d’un problème ?
La complexité de Kolmogorov s’applique à tout objet mathématique, pas forcément à un problème : elle est définie comme la longueur du plus petit script Python calculant l’objet. Mais dans le cas d’un problème, on utilise une autre définition :
La classe de complexité d’un problème est le coût de l’algorithme le plus efficace résolvant ce problème.
Cette définition n’est pas toujours simple à utiliser, parce qu’on ne connaît pas forcément le meilleur algorithme : celui-ci a-t-il déjà été inventé ? Quoi qu’il en soit, la classe des problèmes les plus simples est celle des problèmes résolus par un algorithme en temps polynomial, car si par exemple un problème est résolvable en temps quadratique, si d’aventure on trouvait un meilleur algorithme (mettons, en temps logarithmique), a fortiori le problème resterait résolvable en temps polynomial. La classe des problèmes jugés faciles à résoudre s’appelle P (première lettre de polynomial).
Certains jeux sont jugés inintéressants parce que leur stratégie gagnante est dans P ; parmi eux, le jeu du lièvre et du chien, jeu médiéval pour lequel Berlekamp, Conway et Guy ont trouvé une stratégie gagnante simple ; le jeu de Fort-Boyard, décrit pour la première fois par Bachet et dont la stratégie gagnante ne nécessite qu’une division par 4 ; le jeu de jonction de points inventé par Lucas et appelé lucasta par Conway, dont Lucas décrit une stratégie gagnante simple ; le jeu de Nim créé par Charles Bouton à la fin du XIXe siècle, avec une stratégie gagnante basée sur le binaire ; le jeu bridg-it, créé par David Gale [1], et pour lequel Alfred Lehman a trouvé en 1964 une stratégie gagnante simple, basée sur les matroïdes...
Existe-t-il un algorithme simulant l’intuition ?
La classe de complexité juste au-dessus (ou pas) de P s’appelle NP, le N désignant le non-déterminisme : ce sont les problèmes résolubles en temps polynomial en introduisant du non-déterminisme, chance ou coup de génie. De façon équivalente, ce sont des problèmes pour lesquels, une fois qu’on a trouvé grâce à une bonne dose d’intuition [2] la solution d’un problème, on peut vérifier en temps polynomial que c’est vraiment une solution.
Si un problème est de classe P, alors il est aussi de classe NP (il suffit de ne pas écouter son intuition pour le résoudre en temps polynomial). Lorsqu’un problème semble vraiment être NP sans pour autant être P, on le dit NP-complet. La liste de problèmes NP-complets, forte de centaines voire de milliers de problèmes, comprend certains jeux célèbres à un joueur, comme le sudoku sur n² symboles, Tetris, Super Mario, Pacman et, bien entendu, le solitaire (casse-tête) généralisé...
La question à un million de dollars est de savoir si P=NP, c’est-à-dire si l’intuition est calculable en temps polynomial. Ce problème, apparu au début des années 1970, est toujours un problème ouvert, au point que la fondation Clay en a fait un de ses 7 problèmes du millénaire. Cette conjecture relève d’ailleurs d’un intérêt bien plus pratique que la ludologie, puisque la sécurité d’Internet et en particulier des transactions financières, est basée sur la conjecture selon laquelle P diffère de NP, en tout cas sur la décomposition en facteurs premiers, qui est NP-complète (et personne, en dehors des hackeurs, n’a envie qu’il existe un algorithme en temps polynomial permettant de casser le chiffrement RSA).
Plus compliqué que NP, c’est possible ?
En 1998, Joseph Culberson a réussi à simuler dans le jeu (à un joueur) vidéo Sokoban, une machine de Turing occupant une place mémoire dépendant polynomialement de la taille des données d’entrée. Cela place le jeu Sokoban dans une catégorie plus complexe que NP, à savoir PSPACE (problèmes résolubles en utilisant un temps qui peut dépendre exponentiellement de la taille des données, mais en n’occupant qu’un espace mémoire polynomial). Dans sa thèse de 2006, Robert Hearn invente la logique contrainte dont il montre qu’elle est NP, puis la version nondéterministe qu’il prouve PSPACE. Cela lui permet de retrouver immédiatement le résultat connu sur Sokoban, mais aussi que beaucoup de jeux combinatoires à deux joueurs connus (Reversi, Hex, Amazons, géographie généralisée, chomp (jeu), et même le jeu traditionnel hawaïen konane). En fait, on peut se demander s’il existe des jeux intéressants à deux joueurs qui ne sont pas dans PSPACE. La réponse est oui : des jeux où il n’est pas facile de savoir si une partie dure un temps fini, comme les échecs ou le Go, sont dans EXPTIME donc encore plus complexes que les jeux dits intéressants.
C’est quoi, un bon jeu ?
Sollicité en 1942 pour une conférence sur les jeux mathématiques, Piet Hein, déjà connu pour son invention du cube Soma, a proposé certains critères qui doivent être présents pour qu’un jeu mathématique soit bon. C’est à cette occasion qu’il a inventé Hex comme exemple de bon jeu. On peut résumer sa définition par ces deux contraintes :
- La complexité de Kolmogorov de la règle du jeu doit être petite.
- La complexité de la recherche d’une stratégie gagnante doit être grande.
Un exemple qui nous intéressera dans la suite est le jeu alquerkonane, jugé bon par les très nombreux élèves y ayant déjà joué, et dont la règle est effectivement assez courte, comme la formule Claude (plus bas) :
Le jeu se joue sur un damier (alternance de cases noires et blanches). Les pions noirs sont sur des cases noires, les pions blancs sont sur des cases blanches. Il y a deux sortes de mouvements pour un pion :
- avancer d’une case en diagonale (vers l’avant seulement),
- capturer un pion adverse, en sautant par-dessus, à condition que la case suivante soit vide (le pion y atterrit), dans n’importe quelle direction.
La prise n’est pas obligatoire, mais on ne mange qu’une fois maximum par tour de jeu.
Le premier qui ne peut plus bouger aucun de ses pions perd le jeu.
La conjecture à laquelle est consacré cet article est qu’alquerkonane, bien qu’étant un jeu à deux joueurs, est de complexité NP plutôt que PSPACE : il semble plus simple que Reversi, Hex etc. et surtout que son cousin konane. En effet la preuve de PSPACE-complétude de konane utilise le fait qu’à ce jeu, on peut manger plusieurs fois en un tour, ce qui permet de simuler le transport d’une information binaire le long d’un câble, alors qu’avec alquerkonane le seul moyen de transport d’une information est par le mouvement d’un pion sans capture, et ce transport ne peut se faire que dans un sens (vers le haut).
Apprenant que Claude (IA) a été utilisé pour résoudre un problème de maths, j’ai décidé d’essayer cet outil sur une conjecture : celle selon laquelle la recherche d’une stratégie gagnante à alquerkonane est NP-complète. Sa réaction est intéressante : il commence par douter de ma conjecture parce que tous les jeux mathématiques dont on connaît la complexité sont dans PSPACE et non dans NP. Il me donne une preuve presque complète de sa conjecture. Puis lorsque je mets le doigt sur cette opposition local/global, il change d’avis et conjecture que ce jeu est vraiment NP :
En résumé, Claude est un rat de bibliothèque très impressionnant, ce qui aide (pour la recherche) à obtenir des références. Il est également stimulant par ses erreurs (de calcul ou de raisonnement). Mais ne semble pas capable de trouver la solution d’un tel problème. Il est aussi très flatteur, voire emphatique, sinon encourageant.
La conjecture en est donc toujours une (conjecture). La question suivante a alors porté sur un autre jeu : Sowing impartial. Ce jeu a donc également donné lieu à une discussion avec Claude :
En résumé, les jeux mathématiques à deux joueurs sont à chercher du côté de PSPACE plutôt que NP [3], hormis ceux qui, comme le Go ou les échecs, ne se terminent pas forcément en temps fini, et qui, eux, sont EXPTIME. Pour des jeux comme alquerkonane ou sowing impartial, il est difficile d’estimer la complexité, par manque de structure. Ce qui a alors inspiré le raisonnement par l’absurde suivant :
On sait que Hex est PSPACE. Si Hex était P, alors il existerait un polynôme sur les sommets (vus comme des nombres complexes) de son plateau, dont les zéros donneraient une stratégie gagnante que l’on ne connaît pas. Donc il y a peu de chances qu’il existe un polynôme intéressant s’annulant sur certains entiers d’Eisenstein.
La question a été posée à Claude :
Là, les erreurs sont plus subtiles :
- Claude se trompe de valeur pour ω (argument deux fois trop petit) ; je ne m’en suis rendu compte qu’après avoir vu son dessin pour le jeu Y et certaines de ses affirmations doivent être corrigées.
- Claude confond régulièrement l’origine (0,0) avec le centre du plateau de Hex.
- Claude prétend que jouer le symétrique du coup joué précédemment par l’adversaire, permet de gagner le jeu. Ce n’est pas vrai car le centre du plateau ne peut être joué qu’une seule fois (et de plus, John Forbes Nash a prouvé en 1948 que c’est celui qui joue en premier qui dispose de la stratégie gagnante, à moins de compliquer un peu la règle).
- Claude prétend que tous les entiers relatifs congrus à 2 modulo 3 sont premiers vus comme entiers d’Eisenstein, or 8 est congru à 2 modulo 3 et 8 n’est pas premier.
- Dans son passage sur la norme trichrome, Claude propose cette tactique : choisir la case qui minimise le maximum de (dA, dC, dB), or cette case n’est pas unique, puisque la somme des trois distances est uniforme sur tout le plateau de jeu.
En résumé, les IA génératives peuvent assister à la recherche, mais il faut se méfier de leurs erreurs (notamment de calcul) : tout doit être vérifié, que ce soit les références bibliographiques ou les calculs. Et la complexité de certains jeux mathématiques est peut-être indécidable, d’après l’heuristique suivante : si on pouvait démontrer que alquerkonane ou sowing impartial sont NP sans être PSPACE, on résoudrait une conjecture vieille d’un demi-siècle. Et si, comme l’imagine Claude, on prouve qu’alquerkonane est NP sans être P, on gagne un million de dollars !