L’une des grandes conjectures de la complexité arithmétique en partie dénouée
Le problème « P = ou ≠ à 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 polynomial1 . 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’IEEE2 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 œuvre 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 type RSA 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. Or nos 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. »