Article

La semaine des mathématiques | 15 – 19 mars 2021 | Jour 3

Pour ponctuer la semaine des mathématiques, vos professeurs vous proposent une histoire par jour sur un aspect des mathématiques que vous ne connaissez sans doute pas…encore !

Histoire du mercredi
Annonce

Aujourd’hui « P = NP ? » : est-ce que trouver la solution à un problème est forcément plus difficile que de vérifier si une solution est correcte ?

P = NP ?

Tout le monde connaît le sudoku : Remplir un carré de 9 cases de côté avec les chiffres 1 à 9 de manière à ce que chaque chiffre apparaisse une unique fois sur chaque ligne, chaque colonne et dans chaque “sous-carré”. Je trouve ce jeu un peu compliqué. J’en ai donc inventé un nouveau : le unidoku. C’est la même chose mais avec une seule ligne. C’est plus à mon niveau…

L’unidoku est facile à résoudre. On dit que c’est un problème de classe P. Le sudoku est difficile à résoudre. Mais si on vous donne une solution, il est facile de vérifier que cette solution est valide. On dit que c’est un problème classe NP.


Cette classification est due au chercheur en informatique Stephen Cook et désigne en fait le temps de calcul nécessaire pour un ordinateur pour trouver ou vérifier une solution. Cook remarqua que la découverte d’algorithmes plus efficaces permettait de reclasser certains problèmes de classe NP en classe P. Il se demanda alors : “Est-ce que tous les problèmes NP admettent un algorithme qui permet de le reclasser en P ?” C’est le problème « P=NP ? », qui est un des problèmes du millénaires.

Personne n’a encore trouvé la réponse à cette question. Si cette réponse est “oui”, cela voudrait dire que le sodoku n’est en fait pas plus difficile que le unidoku, du moins pour un ordinateur. Autre petit détail : craquer le code qui protège tous les mots de passe sur internet est un problème de classe NP...

Pour continuer en vidéo (cliquez sur les images)

Moi ça me fait rire
(mais je suis prof de maths…)