Sylvain Perifel

P VS NP : quels problèmes peut-on résoudre efficacement ?

Samedi 12 mars à 15h

 Résumé : La notion de « méthode automatique » de calcul intéresse les mathématiciens depuis longtemps, bien avant l’apparition du premier ordinateur. Au début, la principale question était de savoir si l’on peut tout calculer de cette manière. Puis, suite à l’apparition des premiers ordinateurs avec leurs capacités limitées, la question de la performance devint cruciale : que peut-on calculer efficacement avec ces machines ?

Certains calculs semblent a priori difficiles mais des méthodes efficaces pour les résoudre ont finalement été inventées. En revanche, d’autres calculs résistent aux efforts des informaticiens et on ne sait pas les résoudre rapidement : s’agit-il d’une limitation intrinsèque de nos ordinateurs, ou peut-on espérer trouver un jour des méthodes efficaces ?

Nous verrons les réponses subtiles que la théorie de la complexité algorithmique fournit à ces questions difficiles. L’histoire de cette aventure nous amènera notamment à aborder les problèmes suivants : qu’est-ce qu’un calcul efficace ? Peut-on prouver qu’il existe des calculs difficiles ? Est-il plus facile de vérifier une solution que de la trouver ? L’aléatoire permet-il d’accélérer les calculs ?

Inscription : http://www.ihp.fr/fr/seminaire/mathpark-inscription