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

Publié par Adrien le 13/01/2022 à 09:00
Source: CNRS INS2I
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 (En musique, le mot fondamentale peut renvoyer à plusieurs sens.) dont Sébastien Tavenas, chargé de recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue...) CNRS (Le Centre national de la recherche scientifique, plus connu sous son sigle CNRS, est le plus grand...) au Laboratoire de mathématiques (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide...) du Bourget-du-Lac (LAMA - CNRS / Université de Savoie (Fondée en 1979, l'université de Savoie accueille aujourd'hui plus de 12 000...) 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 (L´informatique - contraction d´information et automatique - est le domaine...) 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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou...) l'enjeu est de savoir si la classe de complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en...) P des problèmes admettant un algorithme de résolution s'exécutant en temps (Le temps est un concept développé par l'être humain pour appréhender le...) polynomial est équivalente à la classe de complexité (La complexité est une notion utilisée en philosophie, épistémologie (par...) 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 (Un chercheur (fem. chercheuse) désigne une personne dont le métier consiste à faire de la...) qui évolue dans le champ (Un champ correspond à une notion d'espace défini:) 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 (Un institut est une organisation permanente créée dans un certain but. C'est...) de mathématiques Clay. Celui ou celle qui parviendra à le résoudre se verra ainsi remettre la somme d'un million (Un million (1 000 000) est l'entier naturel qui suit neuf cent quatre-vingt-dix-neuf...) 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 (Un scientifique est une personne qui se consacre à l'étude d'une science ou des sciences et qui...) du CNRS a toutefois obtenu de sérieuses avancées sur un problème connexe à cette conjecture (En mathématiques, une conjecture est une assertion qui a été proposée comme vraie, mais que...). 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é (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en...) à l'Institut indien de technologie (Le mot technologie possède deux acceptions de fait :) de Bombay et Srikanth Srinivasan, chercheur en informatique fondamentale à l'Université (Une université est un établissement d'enseignement supérieur dont l'objectif est la...) 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 (On nommait dans les années 1960-1980 informaticien ou informaticienne une personne...) 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 (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer,...) de la complexité dans un monde (Le mot monde peut désigner :) de nature arithmétique (L'arithmétique est une branche des mathématiques qui comprend la partie de la...) 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 (Futurs est une collection de science-fiction des Éditions de l'Aurore.) 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é (Il existe différentes définitions de la dureté : pour un solide (minéral ou métal) et...) 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 (En cryptographie, le chiffrement (parfois appelé à tort cryptage) est le procédé grâce auquel...) cryptographique de typeRSA très utilisé pour échanger des données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent...) confidentielles sur Internet (Internet est le réseau informatique mondial qui rend accessibles au public des services...). "À l'heure actuelle, il n'existe aucune méthode capable de prouver que de telles clés de codage (De façon générale un codage permet de passer d'une représentation des...) 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."
Cet article vous a plu ? Vous souhaitez nous soutenir ? Partagez-le sur les réseaux sociaux avec vos amis et/ou commentez-le, ceci nous encouragera à publier davantage de sujets similaires !
Page générée en 0.018 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique