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

Ancien lauréat
Prix d'excellence du CRSNG de 2005

Stephen Cook

Professeur distingué

University of Toronto


Stephen Cook
Stephen Cook

La sécurité de chaque transaction commerciale électronique repose sur une ironie informatique. En effet, la confidentialité de l'information sur votre carte de crédit ne dépend pas de ce que les ordinateurs peuvent faire, mais de ce qu'ils ne peuvent pas faire. C'est une étrangeté qui constitue l'un des plus grands mystères mathématiques du XXIe siècle. Au cours des 35 dernières années, personne n'a versé autant de lumière sur ce mystère et sur d'autres limites computationnelles que Stephen Cook, l'un des trois candidats en nomination pour la prestigieuse Médaille d'or Gerhard-Herzberg en sciences et en génie du CRSNG.

On peut comprendre que l'attention du public se porte principalement sur les choses surprenantes que les ordinateurs nous permettent de faire, allant de la recherche sur Internet au calcul des prévisions météorologiques. Toutefois, lorsqu'Alan Turing, pionnier de la science informatique, établissait les grandes lignes du premier modèle mathématique pour sa machine de Turing en 1936, il avait déjà remarqué qu'il y avait certains types de problèmes mathématiques que sa machine ne pouvait résoudre.

Les possibilités de lacunes ont refait surface avec le développement rapide de l'informatique qui a suivi la Seconde Guerre mondiale. Les scientifiques se trouvaient souvent incapables de développer des algorithmes efficaces ou des méthodes de calcul pour des problèmes particuliers qu'ils essayaient de résoudre. Était-ce parce qu'il leur fallait travailler davantage ou étaient-ils en train de se cogner la tête sur un gros ordinateur qui ne fournirait jamais de réponse? Ce problème est devenu le point d'intérêt central d'une nouvelle discipline informatique qui traite de la théorie de la complexité, un domaine théorique qui essaie d'expliquer la variabilité naturelle de la difficulté des problèmes computationnels.

C'est dans ce premier contexte de réflexion scientifique informatique que Stephen Cook, alors adolescent, a commencé ses études en mathématiques à l'University of Michigan à la fin des années 1950. Étudiant au premier cycle, il a travaillé sur son premier ordinateur – un Bendix G15 à tubes électroniques du Cornell Aeronautical Laboratory, à Buffalo, New York – dans le cadre d'un projet de recherche visant à mettre au point un système d'atterrissage automatisé pour porte-avions. Il faut noter qu'il s'agit d'un problème complexe qui, près de 50 ans plus tard, n'est toujours pas résolu, et l'immensité du défi a profondément façonné l'imagination et la pensée de M. Cook.

« Dans les années 1960, les ordinateurs étaient relativement nouveaux, et l'une des principales questions qu'on se posait était la suivante : Quelle est la difficulté computationnelle intrinsèque des problèmes complexes? », explique M. Cook, depuis son bureau de l'University of Toronto.

En tant qu'étudiant au doctorat à la Harvard University, M. Cook a aiguisé ses capacités intellectuelles relatives à la théorie de la complexité en prouvant les limites computationnelles de la multiplication précise des nombres élevés.

Après avoir obtenu son diplôme, il a décroché un emploi de professeur adjoint de mathématiques à l'University of California, à Berkeley, où son travail touchait à la fois aux mathématiques et à l'informatique. Cependant, lorsqu'on lui a refusé un poste de professeur titulaire au Département de mathématiques, il a accepté un poste au tout nouveau Département d'informatique de l'University of Toronto, dont il aime se rappeler le dynamisme.

Peu après son arrivée en 1970, M. Cook a fait une découverte inspirée qui a changé la façon dont les scientifiques considèrent les problèmes pouvant être résolus par ordinateur dans un délai raisonnable. Au cours d'un symposium sur la théorie informatique tenu en 1971 aux États-Unis, M. Cook a présenté un bref article intitulé « The Complexity of Theorem Proving Procedures ». Cette présentation a donné lieu à l'un de ces moments rares et magiques où les pairs reconnaissent instantanément que le monde de la science a changé. M. Cook a montré comment reconnaître une vaste classe de problèmes connue sous le nom de problèmes NP-complets, qui ne peuvent apparemment pas être résolus efficacement par ordinateur.

Beaucoup de ces problèmes NP-complets font appel à la mise en file d'attente et à l'ordonnancement, un défi majeur dans de nombreuses entreprises, notamment les agences de messagerie qui essaient de maximiser l'efficacité de leurs itinéraires. Les problèmes NP-complets sont caractérisés par le fait que si l'on vous donnait la réponse, vous seriez capable de vérifier rapidement son exactitude, mais l'obtention de cette réponse par ordinateur n'est pas pratique.

Par exemple, imaginez que vous organisez le logement de 400 étudiants universitaires, mais qu'il n'y a que 100 places dans la résidence et que le responsable de la résidence a indiqué les paires d'étudiants incompatibles. Dans ce cas, si quelqu'un vous donnait une liste finale, il serait facile de vérifier si elle comprend des paires d'étudiants incompatibles. Mais la tâche de choisir 100 étudiants est si difficile qu'elle n'est pas pratique du point de vue informatique – le nombre de façons possibles de choisir les 100 étudiants est plus grand que le nombre d'atomes dans l'univers. Autrement dit, l'ordinateur finirait par cracher une réponse, mais le problème est simplement que vous ne seriez pas là pour la recevoir.

Le théoréme de Cook, comme on la connaît maintenant, offrait une façon de classer les problèmes computationnels en problèmes efficacement solubles et en problèmes NP-complets. Depuis ce temps, des milliers de problèmes scientifiques ont été identifiés comme étant NP-complets. Comme on s'est rendu compte qu'il n'était pas pratique de trouver des réponses complètes à ces questions, les chercheurs en sont venus à développer des techniques computationnelles novatrices pour déterminer des réponses approximatives.

À l'heure actuelle, la confidentialité de l'information transmise sur Internet est basée sur l'hypothèse que même en utilisant le superordinateur le plus rapide du monde, personne ne pourrait déchiffrer efficacement dans un délai raisonnable des données encodées.

La quête d'une preuve (ou contre-preuve) mathématique rigoureuse à cette hypothèse fait l'objet de la fameuse question concernant les problèmes P par rapport aux problèmes NP-complets, l'un des fameux problèmes du millénaire à 1 million de dollars du Clay Mathematics Institute.

« Quiconque arrivera à trouver un algorithme qui pourra résoudre efficacement un problème NP-complet gagnera le million, mentionne M. Cook, mais le vrai problème, selon moi, c'est qu'un tel algorithme n'existe pas. Le défi réel consiste à prouver la non-existence de cet algorithme. »

Réalisations

Stephen Cook est la seule personne au Canada à avoir remporté le Prix A.M. Turing décerné par l'Association for Computing Machinery, le prix le plus prestigieux attribué en informatique. Le témoignage qu'on lui a rendu en 1982 se lisait comme suit : Pour l'avancement significatif et profond de notre compréhension de la complexité computationnelle qu'il a suscité. L'exploration des frontières et de la nature de la classe des problèmes NP-complets a été jusqu'à présent l'une des activités les plus dynamiques et importantes de la recherche en informatique.

Le fait d'avoir été activement engagé en recherche pendant quatre décennies n'a pas empêché M. Cook d'être un mentor et un professeur dévoué. En 1989 et en 1995, il a reçu des prix d'enseignement en informatique de l'University of Toronto. Vingt-cinq étudiants ont obtenu leur diplôme de doctorat sous sa supervision. Son premier étudiant, Walter Savitch, a obtenu la notoriété grâce au théorème de Savitch, et a récemment pris sa retraite après une longue carrière à l'University of California, à San Diego. Plus récemment, Toniann Pitassi, qui a obtenu son doctorat en 1992, a remporté le National Science Foundation (United States) Young Investigator Award. Elle a ensuite reçu une bourse du Programme d'appui aux professeurs universitaires du CRSNG, avec laquelle elle est revenue au Canada. Elle est maintenant une collègue de M. Cook à l'University of Toronto, où elle occupe un poste de professeure.

M. Cook a reçu une Bourse commémorative E.W.R. Steacie du CRSNG en 1977 ainsi qu'une bourse de recherche Killam en 1982. Il est membre de la Société royale du Canada et de la Royal Society of London et a été élu membre de la National Academy of Sciences (États-Unis) ainsi que de l'American Academy of Arts and Sciences.

Aperçu biographique

Stephen Arthur Cook est né à Buffalo, New York, en 1939. Il a obtenu un baccalauréat en sciences de l'University of Michigan en 1961, puis sa maîtrise et son doctorat de la Harvard University en 1962 et en 1966, respectivement. De 1966 à 1970, il a été professeur adjoint à l'University of California, à Berkeley. Il a joint les rangs du corps professoral de l'University of Toronto en 1970 à titre de professeur agrégé et a été promu professeur titulaire en 1975, et professeur hors rang en 1985.