Tip:
Highlight text to annotate it
X
Eh bien, je m’intéressais aux ordinateurs. Mais il n’y avait pas vraiment
de départements d’informatique, alors j’ai fait mes études supérieures à Harvard,
au Département de mathématiques. Ma thèse portait sur un
tout nouveau domaine appelé « complexité des calculs informatiques », c’est-à-dire
l’étude des nombres – de la quantité de ressources, de temps et de mémoire
pour résoudre des problèmes. C’était donc une idée nouvelle; alors, je suis venu ici,
à la University of Toronto, où un tout nouveau
Département d’informatique recrutait des spécialistes de haut niveau.
Et c’est là que je suis depuis ce temps.
C’est là que j’ai eu l’idée ingénieuse d’introduire les concepts que nous appelons maintenant
« les problèmes NP-complets ». Cette idée, cet article,
c’est ce qui m’a rendu célèbre.
Maintenant, bien entendu, on connaît des milliers de problèmes NP-complets
et ils sont assez importants pour
influencer les nombreux domaines de l’informatique.
Mais l’un des problèmes NP-complets types
est celui que l’on appelle communément « le problème du vendeur itinérant ».
On vous donne N villes – N est un grand nombre, une centaine
environ, et leur emplacement
sur une carte. Dans quel ordre le vendeur devrait-il se rendre dans ces villes pour que
son trajet soit le plus court possible? Maintenant, si N représente 100,
une factorielle de 100 représente un nombre si grand
qu’aucun ordinateur imaginable ne pourrait examiner les
100 séquences factorielles avant que le Soleil ne devienne une étoile rouge.
Alors, la question mathématique qui se pose ici,
c’est de savoir si l’on peut résoudre chaque problème NP,
le problème de recherche, et s’il existe en réalité une solution calculée en temps polynômial.
Quant à la question P ou NP, c’est une question sans réponse. En fait, c’est
maintenant l’un des sept problèmes du Prix du millénaire affichés
par l’Institut de mathématiques Clay, qui offre un million de dollars
à celui qui pourra résoudre n’importe lequel de ces problèmes.
Il semble donc que c’est l’un des sept grands problèmes mathématiques
non résolus à l’heure actuelle.