Stephen Cook

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Stephen, Arthur et Cook.
Stephen Cook

Stephen Arthur Cook (né en 1939 à Buffalo dans l'État de New York) est un informaticien et mathématicien américano-canadien, qui a apporté plusieurs contributions majeures à la théorie de la complexité. Il est actuellement professeur à l'université de Toronto, dans le département d'informatique, et dans le département de mathématiques.

Stephen Cook a notamment formalisé la notion de NP-complétude. Il est l'auteur de l'article The Complexity of Theorem-Proving Procedures[1], dans lequel il établit en 1971 que le problème SAT est NP-complet. Ce théorème, appelé depuis théorème de Cook, est fondamental en théorie de la complexité et constitue le point de départ des recherches sur le problème P = NP.

Biographie[modifier | modifier le code]

Cook obtient en 1961 un diplôme de Bachelor de l'université du Michigan, puis un master et un PhD de l'université Harvard, en 1962 et 1966 respectivement. En 1966, il rejoint le département de mathématiques de l'université de Californie, Berkeley en tant que professeur assistant. Cependant, son poste n'est pas renouvelé en 1970. Cook rejoint alors l'université de Toronto en tant que professeur assistant, avant d'obtenir le titre de professeur en 1975, puis de professeur d'université en 1985.

Distinctions[modifier | modifier le code]

Références[modifier | modifier le code]

  1. (en) Stephen A. Cook, « The Complexity of Theorem-Proving Procedures », Conference Record of Third Annual ACM Symposium on Theory of Computing (STOC),‎ 1971, p. 151-158 (lire en ligne [PDF])

Liens externes[modifier | modifier le code]