Conseil de recherches en sciences naturelles et en génie du Canada
Symbol of the Government of Canada

Liens de la barre de menu commune

La question à 1 M$

Stephen Cook pourrait vous aider à gagner un million de dollars. Pour ce faire, vous n’avez qu’à répondre à une question d’habileté. Mais il y a un hic : aucun des plus grands experts des mathématiques n’a encore réussi à répondre à la question.

En 1971, M. Cook a publié un article intitulé The Complexity of Theorem-Proving Procedures, qui présentait ce qui a finalement été appelé le « problème P versus NP ». En voici un exemple.

Imaginons qu’un vendeur itinérant doit se rendre dans 100 villes situées aux quatre coins du pays. Dans quel ordre devrait-il visiter ces villes pour que son trajet soit le plus court possible? Le nombre de trajets qu’il pourrait emprunter est si élevé qu’aucun ordinateur ne pourrait trouver la réponse de notre vivant. La question fondamentale devient alors la suivante : existe-t-il pour chaque problème mathématique comme celui du vendeur itinérant une solution qui permettrait de le calculer dans un délai plus court et plus réaliste?

La question soulevée par le professeur d’informatique et de mathématiques de la University of Toronto fait maintenant partie des sept problèmes mathématiques du prix du millénaire (Millennium Prize Problems) offert par le Clay Mathematics Institute, qui remettra un million de dollars à la personne qui trouvera la solution.

En plus de frapper l’imagination, le problème proposé par M. Cook a fait progresser le domaine des mathématiques et du calcul informatisé. L’objectif fondamental de la recherche en mathématiques est de comprendre ce qui peut être connu et prouvé.

Le problème P versus NP consiste à prouver que les problèmes dits « NP-complets » ne peuvent pas être résolus de façon exacte par les ordinateurs. « Les programmeurs mettent souvent en doute ces preuves d’impossibilité, mais la leçon qu’ils doivent en tirer est qu’il faut parfois faire des compromis lorsque l’on conçoit des programmes », déclare M. Cook.

Les travaux de M. Cook ont des retombées directes dans la vie quotidienne de presque tout le monde. Le problème P versus NP est directement lié au domaine du chiffrement qui nous permet, entre autres, d’utiliser en toute sécurité des cartes de crédit dans Internet. En outre, le chercheur a fait des contributions fondamentales à la théorie informatique, à la conception d’algorithmes, aux langages de programmation et à la logique mathématique. Son œuvre toujours grandissante sera probablement citée pendant de nombreuses décennies, et elle contribue à de nombreux autres domaines de recherche.

M. Cook, lauréat de la Médaille d’or Gerhard-Herzberg en sciences et en génie du Canada de 2012 décernée par le Conseil de recherches en sciences naturelles et en génie du Canada, a réalisé des percées importantes dans son domaine et ouvert des pistes de recherche entièrement nouvelles. Les questions qu’il a soulevées font maintenant partie des théories essentielles que tous les diplômés en informatique doivent connaître. Ses travaux lui ont valu le prix A.M. Turing de l’Association for Computing Machinery, la plus haute distinction remise à un chercheur en informatique.

« Je suis très honoré et privilégié d’avoir reçu la Médaille Herzberg. Mais l’aspect le plus gratifiant de cette marque d’honneur est qu’elle est accompagnée de ressources qui aideront toute mon équipe de la University of Toronto à continuer d’avoir des retombées avantageuses », conclut M. Cook.

Vous pouvez regarder une vidéo de Stephen Cook qui parle de ses travaux.