L'idée que certains problèmes de calcul en mathématiques et en informatique peuvent être difficiles ne devraient pas surprendre.Il y a en fait une classe entière de problèmes jugée impossible de résoudre algorithmiquement.Juste en dessous de cette classe, des problèmes légèrement «plus faciles» qui sont moins bien compris - et peuvent être impossibles aussi.
David Gamarnik, professeur de recherche opérationnelle à la MIT Sloan School of Management et à l'Institut de données, de systèmes et de société, concentre son attention sur cette dernière catégorie de problèmes moins étudiés, qui sont plus pertinents pour le monde quotidien car ilsImpliquer le hasard - une caractéristique intégrale des systèmes naturels.Lui et ses collègues ont développé un puissant outil pour analyser ces problèmes appelés la propriété de chevauchement (ou OGP).Gamarnik a décrit la nouvelle méthodologie dans un article récent dans les actes de la National Academy of Sciences.
P ≠ np
Il y a cinquante ans, le problème le plus célèbre en informatique théorique a été formulé. Labeled “P ≠ np," it asks if problems involving vast datasets exist for which an answer can be verified relatively quickly, but whose solution — even if worked out on the fastest available computers — would take an absurdly long time.
The P ≠ np conjecture is still unproven, yet most computer scientists believe that many familiar problems — including, for instance, the traveling salesman problem — fall into this impossibly hard category.Le défi dans l'exemple du vendeur est de trouver l'itinéraire le plus court, en termes de distance ou de temps, à travers n différentes villes.La tâche est facilement gérée lorsque n = 4, car il n'y a que six itinéraires possibles à considérer. But for 30 cities, there are more than 1030 possible routes, and the numbers rise dramatically from there.La plus grande difficulté vient de concevoir un algorithme qui résout rapidement le problème dans tous les cas, pour toutes les valeurs entières de n. Computer scientists are confident, based on algorithmic complexity theory, that no such algorithm exists, thus affirming that P ≠ np.
Il existe de nombreux autres exemples de problèmes intraitables comme celui-ci.Supposons, par exemple, vous avez une table de nombres géants 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 de sorte que ses 100 entrées auront la somme la plus élevée réalisable?«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, la meilleure route à travers les villes, etc.."
Les informaticiens reconnaissent depuis longtemps que vous ne pouvez pas créer un algorithme rapide qui peut, dans tous les cas, résoudre efficacement des problèmes comme la saga du vendeur itinérant. “Such a thing is likely impossible for reasons that are well-understood," Gamarnik notes."Mais dans la vraie vie, la nature ne génère pas de problèmes dans une perspective contradictoire.Il n'essaie pas de vous contrecarrer avec le problème le plus difficile et cuit à la main concevable." In fact, people normally encounter problems under more random, less contrived circumstances, and those are the problems the OGP is intended to address.
Pics et vallées
Pour comprendre ce qu'est l'OGP, il pourrait d'abord être instructif de voir comment l'idée est née.Depuis les années 1970, les physiciens étudient des verres de spin - matériaux aux propriétés des liquides et des solides qui ont des comportements magnétiques inhabituels.La recherche sur les lunettes de spin a donné naissance à une théorie générale des systèmes complexes pertinents pour les problèmes de physique, de mathématiques, d'informatique, de science des matériaux et d'autres domaines.(Ce travail a valu à Giorgio Parisi un prix Nobel de physique en 2021.)
Un problème vexant que les physiciens ont lutté pour essayer de prédire les états énergétiques, et en particulier les configurations d'énergie les plus basses, de différentes structures en verre de spin. The situation is sometimes depicted by a “landscape" of countless mountain peaks separated by valleys, where the goal is to identify the highest peak.Dans ce cas, le pic le plus élevé représente en fait l'état d'énergie le plus bas (bien que l'on puisse retourner l'image autour et chercher au lieu le trou le plus profond). This turns out to be an optimization problem similar in form to the traveling salesman’s dilemma, Gamarnik explains: “You’ve got this huge collection of mountains, and the only way to find the highest appears to be by climbing up each one" — a Sisyphean chore comparable to finding a needle in a haystack.
Les physiciens ont montré que vous pouvez simplifier cette image et faire un pas vers une solution, en tranchant les montagnes à une certaine élévation prédéterminée et en ignorant tout en dessous de ce niveau de coupure.Vous seriez ensuite laissé avec une collection de pics dépassant au-dessus d'une couche uniforme de nuages, chaque point sur ces pics représentant une solution potentielle au problème d'origine.
Dans un article de 2014, Gamarnik et ses coauteurs ont remarqué quelque chose qui avait été auparavant négligé.Dans certains cas, ils ont réalisé que le diamètre de chaque pic sera beaucoup plus petit que les distances entre différents pics. Consequently, if one were to pick any two points on this sprawling landscape — any two possible “solutions" — they would either be very close (if they came from the same peak) or very far apart (if drawn from different peaks). In other words, there would be a telltale “gap" in these distances — either small or large, but nothing in-between.Un système dans cet état, Gamarnik et ses collègues proposés, se caractérise par l'OGP.
“We discovered that all known problems of a random nature that are algorithmically hard have a version of this property" — namely, that the mountain diameter in the schematic model is much smaller than the space between mountains, Gamarnik asserts.«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 s'attaquer à des problèmes particuliers. And it has already enabled them “to mathematically [and] rigorously rule out a large class of algorithms as potential contenders," Gamarnik says."Nous avons appris, en particulier, que les algorithmes stables - ceux dont la sortie ne changera pas beaucoup si l'entrée ne change qu'un peu - échouera à résoudre ce type de problème d'optimisation." This negative result applies not only to conventional computers but also to quantum computers and, specifically, to so-called “quantum approximation optimization algorithms" (QAOAs), which some investigators had hoped could solve these same optimization problems.Maintenant, en raison de Gamarnik et des conclusions de ses co-auteurs, ces espoirs ont été modérés par la reconnaissance 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.
“Whether that’s good news or bad news depends on your perspective," he says.«Je pense que c'est une bonne nouvelle dans le sens où cela nous aide à déverrouiller les secrets de la complexité algorithmique et améliore nos connaissances quant à ce qui est dans le domaine de la possibilité et de ce qui n'est pas.C'est une mauvaise nouvelle dans le sens où cela nous dit que ces problèmes sont difficiles, même si la nature les produit, et même si elles sont générées de manière aléatoire." The news is not really surprising, he adds.«Beaucoup d'entre nous s'y attendaient depuis le début, mais nous avons maintenant une base plus solide sur laquelle faire cette affirmation."
Cela laisse toujours les chercheurs à des années-lumière de pouvoir prouver la non-existence d'algorithmes rapides qui pourraient résoudre ces problèmes d'optimisation dans des contextes aléatoires. Having such a proof would provide a definitive answer to the P ≠ np problem. “If we could show that we can’t have an algorithm that works most of the time," he says, “that would tell us we certainly can’t have an algorithm that works all the time."
Predicting how long it will take before the P ≠ np problem is resolved appears to be an intractable problem in itself.Il est probable qu'il y aura beaucoup plus de pics à gravir, et des vallées à traverser, avant que les chercheurs n'atteignent une perspective plus claire sur la situation.
