La série d’exposés spéciaux visant à présenter les problèmes du Millénaire se poursuit cette semaine. Composée par le Clay Mathematics Institute au tournant du millénaire, la liste de 7 problèmes couvre un large pan des mathématiques modernes en proposant des défis très difficiles et encore tous non résolus, à une exception près !
Ces problèmes sont donc tous difficiles et il est souvent même compliqué de comprendre leur formulation. L’objectif de cette série d’exposés est de familiariser l’audience avec le contexte de chaque problème ainsi que de comprendre en quoi ils sont importants pour le paysage mathématique du 21ème siècle. Bien sûr, on ne saura éviter les aspects techniques, mais l’accent sera également mis sur l’aspect historique de ces problèmes.
Titre: « Problèmes du Millénaire: P vs NP »
Conférencier: Xavier Provençal, maître d’enseignement en mathématiques.
Où et quand: Vendredi 3 juin 2022 à 13h30 (B-1506)
Résumé:
Est-il plus difficile de trouver la solution à un problème que de convaincre les autres que la solution qu’on a trouvée est bonne ? Dans certains cas, notre intuition nous porte à croire que oui. Par exemple, trouver une solution à un système d’équations est habituellement plus difficile que d’en vérifier la validité.
La théorie de la complexité est une branche de l’informatique théorique qui s’intéresse à ce genre de questions. On y définit une hiérarchie de classes de problèmes basée sur la quantité de travail nécessaire pour les résoudre. On définit entre autres les classes P (problèmes pour lesquels une solution est « facile » à trouver) et NP (problèmes pour lesquels une solution est « facile » à valider). En 1971 Stephen Cook et Leonid Levin ont posé la question : est-ce que P = NP ? Autrement dit, existe-t-il un problème pour lequel il est significativement plus facile de valider une solution plutôt que d’en trouver une.
Dans cet exposé, nous allons présenter une introduction à la théorie de la complexité des algorithmes afin de définir formellement les classes P et NP. Dans un deuxième temps, nous présenterons la théorie de la NP-complétude. Cette théorie permet de comprendre toute la portée de cette question, ainsi que ses implications sur de nombreux problèmes algorithmiques concrets.
Guillaume Roy-Fortin, maître d’enseignement en mathématiques
