Découvrir: (P=NP) Elémentaire chèr(e) Watson. "Echec et Math"

En mathématiques, et plus précisément en informatique théorique, le problème P = NP est un problème non résolu, et est considéré par de nombreux chercheurs comme un des plus importants problèmes du domaine, et même des mathématiques en général. L'Institut de mathématiques Clay a inclus ce problème dans sa liste des 7 problèmes du prix du millénaire1, et offre à ce titre 1 000 000 $ à quiconque sera en mesure de prouver P = NP ou P ≠ NP. Ce problème est également le troisième problème de Smale. Très schématiquement, il s'agit de déterminer si le fait de pouvoir vérifier rapidement une solution à un problème implique de pouvoir la trouver rapidement ; ou encore, si ce que nous pouvons trouver rapidement lorsque nous avons de la chance peut être trouvé aussi vite par un calcul intelligent. Il s'agit plus formellement de savoir si la classe de complexité P des problèmes de décision admettant un algorithme de résolution s'exécutant en temps polynomial sur une machine de Turing est équivalente à la classe de complexité NP des problèmes de décision dont la vérification du résultat, une fois celui-ci connu, demande un temps polynomial. Un algorithme qui demande un temps d'exécution polynomial est généralement considéré comme « rapide » (par rapport à un temps d'exécution exponentiel par exemple). Les conséquences de P = NP pourraient être considérables dans de nombreux domaines : cryptologie, informatique, mathématiques, ingénierie, économie. On pourrait même imaginer que celui qui prouverait P = NP ressortirait de l'Institut de mathématiques Clay avec 6 millions de dollars, les implications de la solution pouvant rendre la résolution des autres problèmes du millénaire trivialeFortnow 1. S'il est au contraire avéré que P ≠ NP, cela signifierait qu'une large classe de problèmes sont presque sûrement définitivement hors d'atteinte du calcul dans un temps raisonnable (ou nécessite le développement d'architectures différentes de celles des machines de Turing).

Dans l'épisode "Echec et Math" de la saison 2 de la série

Américaine "Elementary" le problème (P=NP) est supposé résolu ,le Sherlock Homes moderne doit résoudre l'énigme des meurtres de deux mathématiciens.