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.

Quand à 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.