décembre 8, 2022

BreaGeek News

Obtenez toutes les dernières nouvelles et rapports sur la FRANCE ici. Manchettes, politique et culture françaises sur une chaîne d'information

Le chercheur développe un nouvel outil pour comprendre des problèmes de calcul difficiles et apparemment insolubles

Dans certains cas, le diamètre de chaque pic sera beaucoup plus petit que les distances entre les différents pics. Ainsi, si l’on devait choisir deux points quelconques sur ce paysage tentaculaire – c’est-à-dire deux « solutions » possibles – ils seraient soit 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 aura un « écart » révélateur entre ces distances – petit ou grand, mais rien entre les deux. Crédit : David Jamarnik et al.

L’idée que certains problèmes de calcul en mathématiques et en informatique peuvent être difficiles ne devrait pas surprendre. Il existe en fait toute une classe de problèmes pour lesquels il est considéré comme impossible à résoudre mathématiquement. Au-dessous de cette catégorie se trouvent quelques problèmes « plus faciles » qui ne sont pas bien compris – et ils peuvent également être impossibles.


David Jamarnik, professeur de recherche opérationnelle à la MIT Sloan School of Management et à l’Institute for Data, Systems, and Society, concentre son attention sur cette dernière catégorie de problèmes moins étudiés, qui sont plus pertinents dans le monde de tous les jours car ils impliquent Aléatoire—Une caractéristique essentielle des systèmes naturels. Lui et ses collègues ont développé un outil puissant pour analyser ces problèmes appelé la propriété de chevauchement (ou OGP). Gamarnik a décrit la nouvelle méthodologie dans un récent document de recherche en Actes de l’Académie nationale des sciences.

P NP

Il y a cinquante ans, le problème le plus célèbre de l’informatique théorique était formulé. P ≠ NP demande s’il existe des problèmes impliquant d’énormes ensembles de données dont la réponse peut être vérifiée relativement rapidement, mais qui – même en travaillant sur les ordinateurs les plus rapides disponibles – prendraient un temps absurdement long à résoudre.

La conjecture P NP reste à prouver, mais la plupart des informaticiens pensent que de nombreux problèmes familiers, y compris, par exemple, le problème du voyageur de commerce, entrent dans cette catégorie incroyablement difficile. 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 villes différentes. La tâche est facilement gérée lorsque N = 4, car il n’y a que six chemins possibles à considérer. Mais dans 30 villes, il y en a plus de 1030 manières possibles, et les chiffres augmentent de façon exponentielle à partir de là. La plus grande difficulté réside dans la conception d’un fichier algorithme Il résout le problème rapidement 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é computationnelle, qu’il n’existe pas un tel algorithme, confirmant que P NP.

Il existe de nombreux autres exemples de tels problèmes insolubles. Supposons, par exemple, que vous ayez une table de nombres énormes avec des milliers de lignes et des milliers de colonnes. Pouvez-vous trouver, parmi toutes les combinaisons possibles, la disposition exacte de dix lignes et 10 colonnes de telle sorte que leurs cent entrées aient la somme la plus élevée possible ? « Nous les appelons des tâches d’optimisation, car vous essayez toujours de trouver la plus grande ou la meilleure – la plus grande somme de nombres, le meilleur itinéraire à travers les villes, etc. », explique Jamarnik.

Les informaticiens ont compris depuis longtemps qu’on ne peut pas créer un algorithme rapide qui puisse, dans tous les cas, résoudre des problèmes aussi efficacement que la saga du voyageur de commerce. « Il est probable qu’une telle chose serait impossible pour des raisons bien comprises », note Jamarnik. « Mais dans la vraie vie, la nature ne génère pas de problèmes d’un point de vue hostile. Elle n’essaie pas de vous frustrer avec un problème finement sélectionné et le plus difficile imaginable. » En fait, les gens rencontrent généralement des problèmes dans des circonstances plus aléatoires et moins gérées, et ce sont les problèmes que le Partenariat pour un gouvernement ouvert vise à résoudre.

Pics et vallées

Pour comprendre en quoi consiste le Partenariat pour un gouvernement ouvert, il peut être utile de voir d’abord comment l’idée est née. Depuis les années 1970, les physiciens étudient le verre de spin – des matériaux qui ont des propriétés à la fois des liquides et des solides qui ont des comportements magnétiques inhabituels. La recherche sur les verres de spin a donné naissance à une théorie générale des systèmes complexes liés à des problèmes de physique, de mathématiques, d’informatique, de science des matériaux et d’autres domaines. (Ce travail a valu à Giorgio Baresi le prix Nobel de physique 2021.)

Un problème déroutant auquel les physiciens ont été confrontés est d’essayer de prédire l’état d’énergie, en particulier les configurations d’énergie les plus basses, de différentes structures de verre en rotation. La situation est parfois dépeinte dans un « paysage » d’innombrables sommets montagneux séparés par des vallées, où le but est de localiser 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 à la place et rechercher le trou le plus profond). Cela s’avère être un problème d’optimisation similaire dans la forme au dilemme du voyageur de commerce, explique Jamarnik : « Vous avez cet énorme ensemble de montagnes, et il semble que la seule façon de trouver plus haut est de gravir chacune d’entre elles » – une corvée absurde semblable pour trouver une aiguille dans une botte de foin.

Les physiciens ont montré que vous pouvez simplifier cette image et faire un pas vers une solution en coupant les montagnes à une certaine hauteur prédéterminée et en ignorant tout ce qui se trouve en dessous de ce niveau de coupure. Vous laisserez ensuite un groupe de pics proéminents au-dessus d’une couche uniforme de nuages, chaque point de ces pics représentant une solution potentielle au problème d’origine.

Dans un document de recherche de 2014, Jamarnik et ses collègues notent quelque chose auparavant négligé. Ils se sont rendu compte dans certains cas que le diamètre de chaque pic serait beaucoup plus petit que les distances entre les différents pics. Ainsi, si l’on devait choisir deux points quelconques sur ce paysage tentaculaire – c’est-à-dire deux « solutions » possibles – ils seraient soit 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 aura un « écart » révélateur entre ces distances – petit ou grand, mais rien entre les deux. Jamarnik et ses collègues ont suggéré que le système dans ce cas est caractérisé par OGP.

« Nous avons découvert que tous les problèmes connus de nature aléatoire difficile en calcul ont une version de cette propriété » – c’est-à-dire que le diamètre de la montagne dans le modèle schématique est beaucoup plus petit que la distance entre les montagnes, affirme Jamarnik. « Cela fournit une mesure plus précise de la robustesse de l’algorithme. »

Percer les secrets de la complexité des algorithmes

L’avènement de l’OGP pourrait aider les chercheurs à évaluer la difficulté de créer des algorithmes rapides pour résoudre des problèmes spécifiques. Cela leur a déjà permis de « mathématiquement [and] Il a fortement exclu une grande classe d’algorithmes comme concurrents potentiels », a déclaré Jamarnik. Nous avons appris, en particulier, que les algorithmes stables – ceux dont la sortie ne changera pas beaucoup si l’entrée change juste un peu – ne résoudront pas ce genre de problème d’optimisation. « Ce résultat négatif s’applique non seulement aux ordinateurs classiques mais aussi aux ordinateurs quantiques, et plus particulièrement aux « algorithmes d’optimisation d’approximation quantique » (QAOA), dont certains chercheurs avaient espéré résoudre les mêmes problèmes d’optimisation. Maintenant, étant donné les résultats de Jamarnik et Selon les conclusions des co-auteurs, ces espoirs sont tempérés par la reconnaissance que de nombreuses couches d’opérations seront nécessaires pour que les algorithmes de type QAOA réussissent, ce qui peut ê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 notre connaissance de ce qui est dans le domaine de la probabilité et de ce qui ne l’est pas. C’est une mauvaise nouvelle dans le sens où cela nous dit que ces problèmes sont difficile, même si la nature les produit, et même s’ils sont générés aléatoirement ». Il ajoute que la nouvelle n’est pas vraiment surprenante. « Beaucoup d’entre nous s’y attendaient depuis le début, mais nous avons maintenant une base beaucoup plus solide pour faire cette affirmation. »

Cela laisse encore les chercheurs à des années-lumière de pouvoir prouver qu’il n’y a pas d’algorithmes rapides capables de résoudre ces problèmes d’optimisation dans des paramètres aléatoires. Avoir de telles preuves fournirait une réponse définitive au problème P NP. Il dit: « Si nous pouvons prouver que nous ne pouvons pas avoir un algorithme qui fonctionne la plupart du temps, cela nous dit 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 y aura probablement de nombreux sommets à gravir et des vallées à traverser, avant que les chercheurs n’aient une vision plus claire de la situation.


Résolvez de « gros problèmes » avec des algorithmes améliorés par des matériaux 2D


Plus d’information:
David Jamarnik, La propriété Nested Gap : une barrière topologique à l’optimisation des structures stochastiques, Actes de l’Académie nationale des sciences (2021). DOI : 10.1073/pnas.2108492118

la citation: un chercheur développe un nouvel outil pour comprendre des problèmes de calcul difficiles et apparemment insolubles (2022, 10 janvier) Récupéré le 11 janvier 2022 sur https://phys.org/news/2022-01-tool-hard-problems-intractable.html

Ce document est soumis au droit d’auteur. Nonobstant toute utilisation équitable à des fins d’étude ou de recherche privée, aucune partie ne peut être reproduite sans autorisation écrite. Le contenu est fourni à titre informatif seulement.

READ  Des physiciens partent à la recherche d'une lueur quantique durable