Actualite

P=NP : élémentaire, ma chère Watson ?

L’épisode « Echec et Maths » de la série Elementary diffusé récemment a attiré l’attention de Jean-Paul Delahaye et d’Interstices. L’intrigue repose sur la résolution du problème P= NP, fameux problème à un million de dollars.

Un problème est dans P s’il existe un algorithme pour le résoudre en temps raisonnable par rapport à la taille des données : en temps polynomial (ce qui veut dire que le temps de calcul est un polynome de cette taille). Il est dans NP s’il existe un algorithme pour vérifier, en un temps polynomial, qu’on a trouvé une solution, tandis que pour trouver la solution cela peut être d’une complexité explosive (souvent exponentielle en la taille des données). De tels problèmes NP-durs correspondent à des problèmes dont il faut explorer toutes les combinaisons avant de trouver le meilleur résultat recherché.

PDF view