En utilisant 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 d’une complexité absolument diabolique – le plus difficile jamais créé, selon eux.
Les objets sur lesquels travaille cette équipe ne sont en réalité pas vraiment des cristaux à proprement parler : ce sont en fait des quasicristaux. Contrairement aux cristaux normaux, qui sont incroyablement abondants, ces quasicristaux sont également exceptionnellement rare à l’état naturelEn fait, il n’existe qu’une poignée de sources naturelles connues — et elles sont toutes des météorites.
Au-delà de leur rareté, ce qui rend ces matériaux si intéressants est leur architecture. Les atomes sont disposés dans une structure hautement organisée et symétrique, comme les cristaux traditionnels. Mais contrairement à ces derniers, les groupes atomiques ne se répètent pas périodiquement dans l’espace selon un modèle simpleAu lieu de cela, ils présentent des types de symétrie beaucoup plus élaborés.
« Les quasicristaux présentent toutes ces symétries qui ne pourraient jamais exister dans les cristaux, ce qui est assez fascinant. C’est une branche très belle des mathématiques, mais tout le monde 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 Nouveau scientifique.
Cristal, échecs et mathématiques
Les exemples n’étant pas légion, la science a encore beaucoup à apprendre sur les particularités des quasicristaux. Afin de mieux comprendre ces extraterrestres géométriques, l’équipe de Flicker a décidé de créer un algorithme ultra-spécialisé pour décrire leur structure. Et pour y parvenir, ils se sont inspirés… des échecs.
La lignée n’est pas évidente, mais la structure des quasicristaux présente bel et bien des particularités avec un vieux problème logique basé sur les mouvements de la pièce la plus singulière du roi des jeux de société.
Ce casse-tête, appelé Cavalier d’Euler, commence avec un cavalier positionné sur n’importe quelle case de l’échiquier. L’objectif est de lui faire visiter toutes les autres cases sans jamais passer deux fois par la même. Lorsque l’on trace le parcours de ce cavalier, on obtient ce que l’on appelle un circuit hamiltonien, c’est-à-dire qu’il ne passe qu’une seule fois par tous les points d’un graphe.
Or, il s’avère que la structure des atomes dans les quasicristaux suit également cette règle. Et c’est là que ce travail devient intéressant, car cette similitude nous permet d’aborder 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, au point qu’il devient rapidement impossible de calculer la solution par force brute sur notre échelle de temps. En revanche, si nous sommes confrontés à une solution potentielle, il est facile de vérifier rapidement si elle est valide, un peu à la manière d’un puzzle où il suffit d’observer l’image finale.
Le défi est donc de trouver un moyen de résoudre ces problèmes dits NP-complets dans un temps raisonnable (ou plus précisément dans un temps dit polynomial). Et c’est un problème qui rend fous les mathématiciens depuis des décennies. En fait, il entre même dans le champ de P=NPL’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 solution est récompensée par un prix d’un million de dollars. Jusqu’à présent, un seul d’entre eux, la conjecture de Poincaré, a été résolu (par Grigori Perelman en 2010).
Cette équation matérialise une question presque existentielle pour les mathématiciens : Ces problèmes complexes sont-ils vraiment aussi difficiles à résoudre qu’ils le paraissent, ou existe-t-il une solution générale simple que personne n’a encore trouvée pour vous aider à trouver rapidement une solution ?
Si cette hypothèse P=NP devait être confirmée un jour, ce qui est loin d’être certain, les implications seraient énormesCela changerait fondamentalement la nature d’une multitude de problèmes qui sont très importants pour la science moderne, mais considérés aujourd’hui comme pratiquement insolubles (voir notre article ci-dessous pour plus de détails).
Le point important 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 (polynomial) raisonnable, alors Cela signifie qu’il existe également une solution relativement simple à TOUS les autres problèmes NP-completsy compris les circuits hamiltoniens ! Et il s’avère que beaucoup d’entre eux sont particulièrement importants pour la science moderne. Parmi les exemples, citons le problème du voyageur de commerce, dont la résolution rapide éliminerait immédiatement un tas d’énigmes logistiques extrêmement difficiles, ou encore le mécanismes de repliement des protéines que les équipes de DeepMind ont abordé à l’aide de l’apprentissage automatique.
Or, il s’avère que le cavalier d’Euler est un cas particulierBien que les circuits hamiltoniens soient généralement des problèmes NP-complets, il en existe quelques-uns qui peuvent être résolus rapidement par un tour de passe-passe mathématique. Le chevalier d’Euler est l’un d’eux : une solution peut être trouvée rapidement avec une méthode simple, l’algorithme de Warnsdorf. Comme ce problème est étroitement lié à la structure des quasicristaux, les auteurs de ce travail ont donc cherché une méthode analogue à appliquer à leur propre problème.
Et ils en ont trouvé un, qui leur a permis de générer ce labyrinthe incroyablement difficile qui illustre la disposition 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 Alerte scientifiqueces travaux pourraient avoir des implications très concrètes dans des domaines tels que l’optique ou la capture du carbone.
Cependant, cela ne signifie pas que le problème du circuit hamiltonien a été résolu une fois pour toutes ; comme pour le chevalier d’Euler, il s’agit simplement d’un une manière très élégante de simplifier un problème très spécifique, et en aucun cas 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 c’est peut-être un pas dans cette direction. Qui sait ; si une solution rigoureuse émerge un jour, cet ouvrage pourrait être considéré comme l’une des pièces qui ont ouvert la voie à l’une des révolutions les plus importantes de l’histoire des mathématiques.
Le texte de l’étude est disponible ici.
Pour ne rien manquer de l’actualité du Journal du Geek, abonnez-vous sur Google News. Et si vous nous aimez, nous vous proposons une newsletter tous les matins.
