Ancien lauréat
Médaille d'or Gerhard-Herzberg en sciences et en génie du Canada du CRSNG de 2012

Stephen Cook

Informatique et mathématiques

University of Toronto

L’objectif le plus fondamental de la recherche en mathématiques est de comprendre ce qui est connu et prouvé. Les percées y sont rares et lorsqu’il y en a, elles ouvrent des pistes de recherche entièrement nouvelles.

Stephen Cook est l’un des rares chercheurs en mathématiques dont les idées ont engendré de nouveaux domaines de recherche pour les générations actuelles et futures. Ce professeur d’informatique et de mathématiques à la University of Toronto est le lauréat de la Médaille d’or Gerhard-Herzberg en sciences et en génie du Canada de 2012, qui est décernée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG).

L’article publié par M. Cook en 1971, intitulé The complexity of theorem–proving procedures, a donné une signification mathématique aux expressions « calculable avec efficacité » et « prouvable avec efficacité ». Il a regroupé de nombreux problèmes importants qui paraissaient insolubles par l’informatique en supposant qu’un algorithme soluble qui permettrait d’en régler un mènerait à l’élaboration d’algorithmes solubles qui permettraient de les régler tous.

Prenons l’exemple d’un vendeur itinérant qui 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, qui est insoluble par l’informatique, une solution qui permettrait de le calculer avec efficacité?

Les travaux de M. Cook ont eu des retombées durables dans le domaine de l’informatique. Ils lui ont valu le prix A.M. Turing, la plus grande distinction décernée à un chercheur en informatique, et ses travaux représentent maintenant des théories essentielles que tous les diplômés en informatique doivent comprendre. La question fondamentale qu’il a soulevée fait maintenant partie des sept problèmes mathématiques du prix du millénaire. La résolution de l’un de ces problèmes est dotée d’un prix d’un million de dollars américains.

En plus d’avoir fait des contributions reconnues à la théorie de la complexité, M. Cook a fait des contributions fondamentales à la théorie informatique, à la conception d’algorithmes, aux langages de programmation et à la logique mathématique. Son oeuvre toujours grandissante sera probablement citée pendant de nombreuses décennies. Ses travaux ont eu des retombées sur divers domaines des mathématiques et de l’informatique et ont contribué à de nombreux autres domaines de recherche.