Les mathématiques sont souvent considérées comme une science exacte et pour la plupart d’entre nous, elles permettent de résoudre tous les problèmes de calcul. Or, elles se heurtent à certains problèmes encore insolubles, des algorithmes conçus pour les résoudre n’y sont pas parvenus non plus. Parmi ces problèmes, certains sont moins ardus et c’est à eux qu’une équipe du MIT s’est attaquée et a développé un nouvel outil, la propriété d’écart de chevauchement, pour les comprendre.
David Gamarnik, professeur de recherche opérationnelle à la MIT Sloan School of Management et à l’Institute for Data, Systems, and Society, est à la tête de cette équipe qui a tenté de résoudre ces problèmes « plus faciles », potentiellement impossibles eux-aussi mais moins étudiés. Les chercheurs ont développé un outil puissant pour analyser ces problèmes appelé la propriété d’écart de chevauchement (ou OGP). David Gamarnik lui a consacré un article publié dans les « Actes de l’Académie nationale des sciences. »
P ≠ NP
Le problème est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes. Il questionne sur l’existence de problèmes impliquant de vastes ensembles de données pour lesquels une réponse peut être vérifiée rapidement, mais dont la solution (même si elle est élaborée sur les ordinateurs disponibles les plus rapides) prendrait un temps très long. Il fait partie des sept problèmes du « prix du millénaire » pour lesquels l’Institut de mathématiques Clay offre un million de dollars à la personne capable de résoudre l’un d’eux.
La conjecture P ≠ NP n’est toujours pas prouvée, mais la plupart des informaticiens pensent que de nombreux problèmes connus comme celui le problème du voyageur de commerce, entrent dans cette catégorie incroyablement difficile.
C’est sous forme de jeu que William Rowan Hamilton a posé pour la première fois ce problème, en 1859. L’énoncé initial était le suivant : « Un voyageur de commerce doit visiter une et une seule fois un nombre défini de villes et revenir à son point d’origine. Trouvez l’ordre de visite des villes qui minimise la distance totale parcourue par le voyageur ». La solution est aisée lorsque N = 4, car il n’y a que six itinéraires possibles à considérer. Mais pour 30 villes, il y a plus de 10 30 itinéraires possibles, et les chiffres augmentent considérablement à partir de là. La plus grande difficulté vient de la conception d’un algorithme qui résout rapidement le problème dans tous les cas, pour toutes les valeurs entières de N. Les informaticiens sont convaincus, sur la base de la théorie de la complexité algorithmique, qu’aucun algorithme de ce type n’existe, affirmant ainsi que P ≠ NP. David Gamarnik explique:
«Une telle chose est probablement impossible pour des raisons bien comprises. Mais dans la vraie vie, la nature ne génère pas de problèmes d’un point de vue contradictoire. Il n’essaie pas de vous contrecarrer avec le problème le plus difficile et trié sur le volet imaginable. En fait, les gens rencontrent normalement des problèmes dans des circonstances plus aléatoires et moins artificielles, et ce sont les problèmes que l’OGP est censé résoudre.»
Pics et vallées
Depuis les années 1970, les physiciens étudient les verres de spin, des matériaux aux propriétés à la fois liquides et solides qui ont des comportements magnétiques inhabituels. Ils cherchent à prédire les états d’énergie, en particulier les plus basses, des différentes structures de verre de spin. La situation est parfois dépeinte par un « paysage » d’innombrables sommets montagneux séparés par des vallées, où le but est d’identifier le plus haut sommet. Dans ce cas, le pic le plus élevé représente en fait l’état d’énergie le plus bas (bien que l’on puisse inverser l’image et rechercher à la place le trou le plus profond). David Gamarnik déclare :
«Cela s’avère être un problème d’optimisation similaire dans sa forme au dilemme du voyageur de commerce : vous avez cette énorme collection de montagnes, et la seule façon de trouver la plus haute semble être de gravir chacune d’entre elles»
Pour simplifier leur travail, les physiciens n’ont envisagé que la hauteur des pics de ces montagnes, David Gamarnik et ses collègues se sont attachés à leur diamètre : dans certains cas, le diamètre de chaque pic est beaucoup plus petit que les distances entre les différents pics. Par conséquent, si l’on devait choisir deux points quelconques de ce paysage, il y aurait deux solutions possibles : soit ils seraient très proches (s’ils provenaient du même sommet), soit très éloignés (s’ils provenaient de sommets différents). En d’autres termes, il y aurait un «écart» révélateur dans ces distances, petit ou grand, mais rien entre les deux. Un système dans cet état, proposé par David Gamarnik et ses collègues, est caractérisé par l’OGP. David Gamarnik affirme :
«Nous avons découvert que tous les problèmes connus de nature aléatoire qui sont algorithmiquement difficiles ont une version de cette propriété – à savoir que le diamètre de la montagne dans le modèle schématique est beaucoup plus petit que l’espace entre les montagnes. Cela fournit une mesure plus précise de la dureté algorithmique.»
Percer les secrets de la complexité algorithmique
L’OGP peut permettre d’évaluer la difficulté à créer des algorithmes rapides pour résoudre des problèmes particuliers. David Gamarnik explique que cela leur a déjà permis :
«d’exclure mathématiquement [et] rigoureusement une grande classe d’algorithmes en tant que candidats potentiels. Nous avons appris, en particulier, que les algorithmes stables – ceux dont la sortie ne changera pas beaucoup si l’entrée ne change que peu – échoueront à résoudre ce type de problème d’optimisation.»
Ce résultat négatif s’applique non seulement aux ordinateurs conventionnels, mais aussi aux ordinateurs quantiques et, plus précisément, aux soi-disant «algorithmes d’optimisation par approximation quantique» (QAOA), dont certains chercheurs espéraient qu’ils pourraient résoudre ces mêmes problèmes d’optimisation.
Les chercheurs semblent encore très loin de prouver l’inexistence d’algorithmes rapides qui pourraient résoudre ces problèmes d’optimisation dans des contextes aléatoires. Avoir une telle preuve fournirait une réponse définitive au problème P ≠ NP. David Gamarnik conclut :
«Si nous pouvions montrer que nous ne pouvons pas avoir un algorithme qui fonctionne la plupart du temps, cela nous dirait que nous ne pouvons certainement pas avoir un algorithme qui fonctionne tout le temps.»
