culturoscoPe

En 2000, l’Institut de mathématiques Clay décida d’attribuer un prix d’un million de dollars à qui trouverait la solution à l’un des sept problèmes mathématiques réputés insurmontables. Parmi ceux-là, le problème P=NP, qui vient de l'informatique, peut s'énoncer sans formule : « Un problème dont la solution est facile à vérifier est-il aussi facile à résoudre ? » (Exemple : si on donne une grille de Sudoku complétée, c'est facile de vérifier que la solution est correcte ; mais remplir la grille vierge paraît plus difficile). L'exposé précisera les mots « facile » et « difficile », en lien avec la vitesse d'exécution des algorithmes, et discutera les implications mathématiques et philosophiques du problème P=NP.