Posté par Adrien le Jeudi 13/01/2022 à 09:00

P = NP ? Une conjecture à 1.000.000 $ en partie dénouée

Le problème "P = NP ou P ≠ NP" est une assertion relevant de l’informatique fondamentale considérée par de nombreux spécialistes comme l’une des plus importantes questions de ce domaine. Trois chercheurs en informatique fondamentale dont Sébastien Tavenas, chargé de recherche CNRS au Laboratoire de mathématiques du Bourget-du-Lac (LAMA - CNRS / Université de Savoie Mont-Blanc) ont récemment apporté une contribution significative à cette question particulièrement complexe. La qualité de leur travail a été saluée par le Best paper Award lors d’un symposium sur les fondements de l'informatique organisé par l’Institute of Electrical and Electronics Engineers (IEEE).

Réussir à démontrer que P = NP ou au contraire que P ≠ NP constitue l’un des principaux problèmes ouverts de l'informatique fondamentale. Tout l’enjeu est de savoir si la classe de complexité P des problèmes admettant un algorithme de résolution s'exécutant en temps polynomial est équivalente à la classe de complexité NP qui englobe les problèmes de décision dont la vérification du résultat, une fois celui-ci connu, demande un temps polynomial. Pour tout chercheur qui évolue dans le champ disciplinaire de l’informatique fondamentale, ce problème est une sorte de Graal. Il compte d’ailleurs parmi les sept défis mathématiques réputés insurmontables, posés en 2000 par l'Institut de mathématiques Clay. Celui ou celle qui parviendra à le résoudre se verra ainsi remettre la somme d'un million de dollars de la part de cette fondation américaine.

"Intuitivement, cette question revient à essayer de montrer que certains problèmes classiques ne peuvent être résolus rapidement par un ordinateur", résume Sébastien Tavenas, chercheur en informatique fondamentale au LAMA. Bien qu’il ne soit pas parvenu à relever ce défi à un million de dollars, le scientifique du CNRS a toutefois obtenu de sérieuses avancées sur un problème connexe à cette conjecture. Ce résultat qui est à l’origine de l’article récompensé par le Best paper award lors du dernier symposium FOCS de l’IEEE est l'aboutissement d’une collaboration initiée il y a déjà plusieurs années avec deux chercheurs indiens renommés: Nutan Limaye, professeure d'informatique spécialiste de la théorie de la complexité à l’Institut indien de technologie de Bombay et Srikanth Srinivasan, chercheur en informatique fondamentale à l’Université d’Aarhus (Danemark).

Les travaux menés par les trois scientifiques sont une première étape vers la conjecture de Valiant. Cette question énoncée en 1979 par le célèbre informaticien britannique Leslie Valiant est l'analogue algébrique du problème P versus NP. En informatique fondamentale cette transposition est dénommée VP versus VNP. En mettant en oeuvre la théorie de la complexité dans un monde de nature arithmétique l’équipe est, d’une certaine façon, parvenue à escamoter la complexité des circuits logiques qui caractérise habituellement le problème P versus NP. "En contournant cette difficulté, nous avons pu montrer que certains problèmes arithmétiques ne peuvent être calculés rapidement en profondeur constante en utilisant seulement des opérations arithmétiques », explique Sébastien Tavenas. Un tel résultat conforte le fait que P NP au détriment de P = NP c’est-à-dire que certains calculs sont impossibles à résoudre en un temps polynomial.

Au-delà de ces avancées qui démontrent que la conjecture de Valiant est vraie lorsqu’on se restreint aux circuits de profondeur constante, les travaux de Sébastien Tavenas et ses collègues ouvrent la voie à de futurs travaux prometteurs pour la communauté scientifique de la complexité algébrique qui dispose d’un arsenal de techniques mathématiques très étoffé pour démontrer la dureté d’un problème tel que P versus NP. Bien que ces travaux restent de nature purement fondamentale, ils pourraient en outre aboutir à de nouvelles applications notamment dans le domaine du chiffrement cryptographique de typeRSA très utilisé pour échanger des données confidentielles sur Internet. "À l'heure actuelle, il n’existe aucune méthode capable de prouver que de telles clés de codage sont inviolables si ce n’est le fait que personne n’est jusqu’ici parvenu à casser ces systèmes de sécurité particulièrement complexes, confirme Sébastien Tavenas. Ornos résultats laissent entrevoir de potentiels cheminements mathématiques capables de démontrer que les clés de sécurité cryptographique sont réellement incassables à partir de méthodes de calcul arithmétiques."
Dernières actualités
En analysant les propriétés de la lumière émise par une diode électroluminescente...
Il y a 4 500 ans, en Mésopotamie, l’élite utilisait pour se déplacer et pour faire la guerre...
Nous vivons dans une "bulle" d’environ 1000 années-lumière de large, à la surface de laquelle...
Mars possède une basse atmosphère encline à la turbulence. Sa fine atmosphère, généralement...
Une bactérie potentiellement mortelle pour les porcs est apparue pour la première fois chez des...
Les diodes électroluminescentes ou LED, composants des ampoules basse consommation actuelles, sont...
Une équipe internationale comprenant des chercheurs français, issus notamment de l’Observatoire...
Une équipe internationale (France, Angleterre, USA, Danemark) de scientifiques a estimé les taux...
En plus de la vieillesse et de certaines maladies sous-jacentes, la génétique peut avoir une...
La mission PLATO de l'ESA a reçu le feu vert pour poursuivre son développement après la revue...
Si 2021 n’a été "que" la sixième année la plus chaude en 150 ans, elle fait partie d’une...
Des chercheurs de l'Irig décrivent pour la première fois les voies d'entrée de l'uranium dans...
La communauté scientifique s’intéresse de plus en plus aux échauffements stratosphériques1....
Les astronomes ont poussé plusieurs soupirs de soulagement depuis Noël. Le télescope James-Webb...
L'altération chimique des roches a un impact significatif sur la régulation du climat mondial à...
Un groupe international de 78 chercheurs de 49 institutions, incluant le CEA-Irfu, détaille les...
Une équipe de recherche de l’UNIGE et des HUG est parvenue à identifier certains signaux...
Des espaces de travail collaboratifs homme-robot le long de la ligne de production pourraient...
Il y a bien longtemps que les livres consacrés aux régimes alimentaires ou aux conseils de santé...
Des scientifiques de l’UNIGE ont découvert que le gras pourrait aider le pancréas à...
Ce site fait l'objet d'une déclaration à la CNIL
sous le numéro de dossier 1037632
Informations légales