En s’appuyant sur les échecs et la géométrie fractale pour mieux comprendre la structure d’un type de cristal particulièrement exotique, des physiciens britanniques et suisses ont conçu un algorithme qui s’est avéré capable de produire un labyrinthe à la complexité absolument diabolique — le plus difficile jamais créé selon eux.
Les objets sur lesquels travaille cette équipe ne sont en fait pas tout à fait des cristaux à proprement parler : il s’agit en fait de quasicristaux. À l’inverse des cristaux normaux qui sont incroyablement abondants, ces quasicristaux sont aussi exceptionnellement rares à l’état naturel. En fait, il n’en existe qu’une poignée de sources naturelles connues — et il s’agit à chaque fois de météorites.
Au-delà de leur rareté, ce qui rend ces matériaux si intéressants, c’est que leur architecture. Les atomes sont arrangés selon une structure hautement organisée et symétrique, comme les cristaux traditionnels. Mais à la différence de ces derniers, les groupes atomes ne se répètent pas périodiquement dans l’espace en suivant un motif simple. À la place, ils présentent des types de symétrie beaucoup plus élaborés.
« Les quasi-cristaux ont toutes ces symétries qui ne pourraient en aucun cas exister dans les cristaux, ce qui est assez fascinant. C’est une très belle branche des mathématiques — mais n’importe qui peut en apprécier la beauté directement, sans avoir besoin d’en comprendre les détails », explique Felix Flicker, co-auteur de l’étude cité par New Scientist.
Du cristal, des échecs et des maths
Puisque les exemples ne se bousculent pas au portillon, la science a encore beaucoup de choses à apprendre sur les particularités des quasicristaux. Afin de mieux comprendre ces aliens géométriques, l’équipe de Flicker a décidé de créer un algorithme ultraspécialisé pour en décrire la structure. Et pour y parvenir, ils se sont inspirés… des échecs.
La filiation n’est pas évidente, mais la structure des quasi-cristaux présente en effet des particularités avec un vieux problème de logique basé sur les déplacements de la pièce la plus singulière du roi des jeux de plateau.
Ce puzzle dit du Cavalier d’Euler commence avec un cavalier positionné sur n’importe quelle case de l’échiquier. L’objectif, c’est de lui faire visiter toutes les autres cases sans jamais repasser deux fois par la même. Lorsqu’on trace le parcours de ce cavalier, on obtient ce qu’on appelle un circuit hamiltonien, c’est-à-dire qu’il passe une seule fois par tous les points d’un graphe.
Or, il se trouve que la structure des atomes dans les quasicristaux suit aussi cette règle. Et c’est là que ces travaux deviennent croustillants, car cette similitude permet d’appréhender le problème sous l’angle de la théorie de la complexité.
Une incursion dans la théorie de la complexité
En général, trouver un circuit hamiltonien est ce qu’on appelle un problème NP-complet. Ce terme désigne un problème dont la complexité augmente de manière exponentielle avec le nombre d’éléments, à tel point qu’il devient vite impossible de calculer la solution par force brute à notre échelle de temps. En revanche, si l’on se retrouve face à une solution potentielle, il est facile de vérifier rapidement si elle est valide, un peu comme un puzzle où il suffit d’observer l’image finale.
Tout l’enjeu, c’est donc de trouver une façon de résoudre ces problèmes dits NP-complets en un temps raisonnable (ou plus précisément en un temps dit polynomial). Et c’est un problème qui fait tourner les mathématiciens en bourrique depuis des décennies. En fait, cela rentre même dans le giron de P=NP, un des fameux Problèmes du Prix du Millénaire. Il s’agit d’une liste de sept problèmes mathématiques majeurs dont la résolution s’accompagne d’un prix d’un million de dollars. Jusqu’à présent, seul un d’entre eux, la Conjecture de Poincaré, a été résolu (par Grigori Perelman en 2010).
Cette équation matérialise une question quasi existentielle pour les mathématiciens : ces problèmes complexes sont-ils vraiment aussi difficiles à aborder qu’ils en ont l’air, ou existe-t-il une solution générale simple que personne n’a encore trouvée pour chercher une solution rapidement ?
Si cette hypothèse P=NP était confirmée un jour, ce qui est loin d’être acquis, les implications seraient énormes. Cela changerait fondamentalement la nature d’une foule de problèmes très importants pour la science moderne, mais aujourd’hui considérés comme quasiment insolubles (voir notre article ci-dessous pour plus de détails).
Le point important, c’est que tous les spécialistes de la théorie de la complexité s’accordent sur un point : ils considèrent que s’il existe un algorithme pour résoudre un seul problème NP-complet en un temps raisonnable (polynomial), alors cela signifie qu’il existe aussi une solution relativement simple à TOUS les autres problèmes NP-complets, dont les circuits hamiltoniens ! Et il se trouve que bon nombre d’entre eux sont exceptionnellement importants pour la science moderne. On peut citer le problème du voyageur du commerce, dont la résolution rapide supprimerait immédiatement un tas de casse-têtes logistiques extrêmement ardus, ou les mécanismes du repli des protéines auquel les équipes de DeepMind se sont attaquées grâce au machine learning.
Or, il se trouve que le cavalier d’Euler est un cas particulier. Même si les circuits hamiltoniens sont généralement des problèmes NP-complets, il y en a quelques-uns qui peuvent être résolus rapidement grâce à quelques tours de passe-passe mathématiques. Le cavalier d’Euler en fait partie : on peut rapidement trouver une solution grâce à une méthode simple, l’algorithme de Warnsdorf. Puisque ce problème est intimement lié à la structure des quasicristaux, les auteurs de ces travaux ont donc cherché une méthode analogue pour l’appliquer à leur propre problème.
Et ils en ont trouvé une, ce qui leur a permis de générer ce labyrinthe incroyablement difficile qui illustre l’arrangement des atomes dans ces matériaux.
Pas une preuve de P=NP, mais des applications concrètes intéressantes
Selon les chercheurs cités par ScienceAlert, ces travaux pourraient avoir des implications très concrètes dans des domaines comme l’optique ou la capture du carbone.
En revanche, cela ne signifie en aucun cas que le problème des circuits hamiltoniens a été résolu une fois pour toutes ; comme pour le Cavalier d’Euler, il s’agit simplement d’une façon très élégante de simplifier un problème bien précis, et en aucun cas d’une solution générale.
Par extension, ce n’est pas non plus une réponse à l’hypothèse P=NP et à tous les autres problèmes NP-complets… mais il s’agit peut-être d’un pas dans cette direction. Qui sait ; si une solution rigoureuse finit par émerger un jour, on se souviendra peut-être de ces travaux comme l’une des pièces qui ont ouvert la voie à une révolution parmi les plus importantes de l’histoire des mathématiques.
Le texte de l’étude est disponible ici.
🟣 Pour ne manquer aucune news sur le Journal du Geek, abonnez-vous sur Google Actualités. Et si vous nous adorez, on a une newsletter tous les matins.
