Certains problèmes de calcul difficiles, illustrés par la recherche du plus haut sommet dans un “paysage” d’innombrables pics montagneux séparés par des vallées, peuvent tirer parti de la propriété de chevauchement des écarts : À une “altitude” suffisamment élevée, deux points quelconques seront soit proches, soit éloignés l’un de l’autre, mais rien entre les deux.
David Gamarnik a développé un nouvel outil, la propriété de chevauchement, pour comprendre les problèmes de calcul qui semblent insolubles.
L’idée que certains problèmes de calcul en mathématiques et en informatique puissent être difficiles à résoudre ne devrait pas surprendre. Il existe, en effet, une classe entière de problèmes réputés impossibles à résoudre de manière algorithmique. Juste en dessous de cette classe se trouvent des problèmes un peu plus “faciles”, moins bien compris – et qui peuvent aussi être impossibles.
David Gamarnik, professeur de recherche opérationnelle à l’Université de Californie du Sud. MIT Sloan School of Management et de l’Institute for Data, Systems, and Society, concentre son attention sur la dernière catégorie de problèmes, moins étudiée, qui est plus pertinente dans le monde quotidien parce qu’elle implique le caractère aléatoire – une caractéristique intégrale des systèmes naturels. Avec ses collègues, il a mis au point un outil puissant pour analyser ces problèmes, appelé la propriété de l’écart de chevauchement (ou OGP). M. Gamarnik a décrit cette nouvelle méthodologie dans un article récent paru dans l’article Proceedings of the National Academy of Sciences.
P ≠ NP
Il y a cinquante ans, le problème le plus célèbre de l’informatique théorique était formulé. Étiqueté “P ≠ NP“, il demande s’il existe des problèmes impliquant de vastes ensembles de données pour lesquels une réponse peut être vérifiée relativement rapidement, mais dont la solution – même si elle est élaborée sur les ordinateurs les plus rapides disponibles – prendrait un temps absurdement long.
La conjecture P ≠ NP n’est toujours pas prouvée, mais la plupart des informaticiens pensent que de nombreux problèmes familiers – dont, par exemple, le problème du voyageur de commerce – entrent dans cette catégorie de difficulté impossible. Le défi dans l’exemple du vendeur est de trouver le chemin le plus court, en termes de distance ou de temps, par N villes différentes. La tâche est facilement gérée lorsque N=4, car il n’y a que six routes possibles à considérer. Mais pour 30 villes, il y en a plus de 1030 routes possibles, et les chiffres augmentent considérablement à partir de là. La plus grande difficulté réside dans 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’un tel algorithme n’existe pas, affirmant ainsi que P ≠ NP.
Dans certains cas, le diamètre de chaque pic sera beaucoup plus petit que les distances entre les différents pics. Par conséquent, si l’on devait choisir deux points quelconques dans ce paysage tentaculaire – deux “solutions” possibles – ils seraient soit très proches (s’ils proviennent du même pic), soit très éloignés (s’ils proviennent de pics différents). En d’autres termes, il y aurait un “écart” révélateur dans ces distances – soit petit, soit grand, mais rien entre les deux. Crédit : Image fournie par les chercheurs.
Il existe de nombreux autres exemples de problèmes insolubles comme celui-ci. Supposons, par exemple, que vous ayez un tableau géant de nombres avec des milliers de lignes et des milliers de colonnes. Pouvez-vous trouver, parmi toutes les combinaisons possibles, la disposition précise de 10 lignes et 10 colonnes telle que ses 100 entrées auront la somme la plus élevée possible ? “Nous les appelons des tâches d’optimisation”, dit Gamarnik, “parce que vous essayez toujours de trouver le plus grand ou le meilleur – la plus grande somme de chiffres, le meilleur itinéraire à travers les villes, et ainsi de suite.”
Les informaticiens reconnaissent depuis longtemps qu’il est impossible de créer un algorithme rapide qui puisse, dans tous les cas, résoudre efficacement des problèmes comme la saga du voyageur de commerce. “Une telle chose est probablement impossible pour des raisons qui sont bien comprises”, note Gamarnik. “Mais dans la vie réelle, la nature ne génère pas de problèmes dans une perspective contradictoire. Elle n’essaie pas de vous contrecarrer avec le problème le plus difficile et le plus trié sur le volet qui soit.” En fait, les gens rencontrent normalement des problèmes dans des circonstances plus aléatoires et moins artificielles, et ce sont ces problèmes que le PGO vise à résoudre.
Pics et vallées
Pour comprendre ce qu’est le PGO, il est d’abord intéressant de voir comment l’idée est née. Depuis les années 1970, les physiciens étudient les verres de spin, des matériaux dont les propriétés sont à la fois liquides et solides et qui présentent des caractéristiques inhabituelles.comportements magnétiques. La recherche sur les verres de spin a donné naissance à une théorie générale des systèmes complexes qui s’applique à des problèmes de physique, de mathématiques, d’informatique, de science des matériaux et d’autres domaines. (Ces travaux ont valu à Giorgio Parisi un prix Nobel de physique en 2021).
L’un des problèmes épineux auxquels les physiciens se sont heurtés consiste à essayer de prédire les états d’énergie, et en particulier les configurations d’énergie les plus basses, de différentes structures de verre de spin. La situation est parfois décrite par un “paysage” composé d’innombrables pics montagneux séparés par des vallées, où le but est d’identifier le pic le plus élevé. 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 chercher plutôt le trou le plus profond). Il s’agit d’un problème d’optimisation similaire au dilemme du voyageur de commerce, explique Gamarnik : “Vous avez cette énorme collection de montagnes, et la seule façon de trouver la plus haute semble être de grimper sur chacune d’elles” – une tâche sisyphéenne comparable à la recherche d’une aiguille dans une botte de foin.
Les physiciens ont montré qu’il est possible de simplifier ce tableau, et de faire un pas vers une solution, en découpant les montagnes à une certaine altitude prédéterminée et en ignorant tout ce qui se trouve en dessous de ce niveau de coupure. On se retrouverait alors avec une série de pics dépassant d’une couche uniforme de nuages, chaque point de ces pics représentant une solution potentielle au problème initial.
Dans un article de 2014, Gamarnik et ses coauteurs ont remarqué quelque chose qui avait été négligé auparavant. Dans certains cas, ont-ils réalisé, le diamètre de chaque pic sera beaucoup plus petit que les distances entre les différents pics. Par conséquent, si l’on choisissait deux points quelconques dans ce paysage tentaculaire – deux “solutions” possibles – ils seraient soit très proches (s’ils proviennent du même pic), soit très éloignés (s’ils proviennent de pics différents). En d’autres termes, il y aurait un “écart” révélateur dans ces distances – soit petit, soit grand, mais rien entre les deux. Selon Gamarnik et ses collègues, un système dans cet état est caractérisé par l’OGP.
“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 des montagnes dans le modèle schématique est beaucoup plus petit que l’espace entre les montagnes, affirme Gamarnik. “Cela fournit une mesure plus précise de la dureté algorithmique”.
Déverrouiller les secrets de la complexité algorithmique
L’émergence de l’OGP peut aider les chercheurs à évaluer la difficulté de créer des algorithmes rapides pour résoudre des problèmes particuliers. Et elle leur a déjà permis de “mathématiser” la complexité des algorithmes. [and] d’exclure rigoureusement une grande classe d’algorithmes en tant que concurrents potentiels”, déclare M. Gamarnik. “Nous avons appris, en particulier, que les algorithmes stables – ceux dont la sortie ne change pas beaucoup si l’entrée ne change que légèrement – échouent à résoudre ce type de problème d’optimisation.” Ce résultat négatif s’applique non seulement aux ordinateurs classiques, mais aussi aux ordinateurs quantiques et, plus précisément, aux algorithmes dits “d’optimisation par approximation quantique” (QAOA), dont certains chercheurs avaient espéré qu’ils pourraient résoudre ces mêmes problèmes d’optimisation. Aujourd’hui, grâce aux découvertes de Gamarnik et de ses co-auteurs, ces espoirs ont été tempérés par la reconnaissance du fait que de nombreuses couches d’opérations seraient nécessaires pour que les algorithmes de type QAOA réussissent, ce qui pourrait être techniquement difficile.
“Que ce soit une bonne ou une mauvaise nouvelle dépend de votre point de vue”, dit-il. “Je pense que c’est une bonne nouvelle dans le sens où cela nous aide à percer les secrets de la complexité algorithmique et améliore nos connaissances sur ce qui est du domaine du possible et ce qui ne l’est pas. C’est une mauvaise nouvelle dans le sens où elle nous dit que ces problèmes sont difficiles, même si la nature les produit, et même s’ils sont générés de manière aléatoire.” La nouvelle n’est pas vraiment surprenante, ajoute-t-il. “Beaucoup d’entre nous s’y attendaient depuis le début, mais nous disposons maintenant d’une base plus solide pour faire cette affirmation.”
Les chercheurs sont donc encore à des années-lumière de pouvoir prouver l’inexistence d’algorithmes rapides qui pourraient résoudre ces problèmes d’optimisation dans des contextes aléatoires. L’obtention d’une telle preuve apporterait une réponse définitive au problème P ≠ NP. “Si nous pouvions montrer que nous ne pouvons pas avoir un algorithme qui fonctionne la plupart du temps, dit-il, cela nous dirait que nous ne pouvons certainement pas avoir un algorithme qui fonctionne tout le temps.”
Prédire combien de temps il faudra avant que le problème P ≠ NP soit résolu semble être un problème insoluble en soi. Il est probable qu’il y aura encore beaucoup de pics à gravir, et de vallées à traverser, avant que les chercheurs n’aient une perspective plus claire de la situation.
Référence :”La propriété de l’écart de chevauchement : A topological barrier to optimizing over random structures” par David Gamarnik, 12 octobre 2021, Actes de l’Académie nationale des sciences.
DOI : 10.1073/pnas.2108492118