L'article de 1971 intitulé The Complexity of Theorem Proving Procedures a établi les fondements formels du problème P contre NP, une question centrale en informatique qui reste non résolue aujourd'hui. Rédigé par Stephen Cook, cet ouvrage a introduit le concept de NP-complétude, modifiant la manière dont les mathématiciens et les informaticiens catégorisent la difficulté inhérente des tâches de calcul.
Fondation académique
Né à Buffalo en 1939, Cook a fait ses études supérieures aux États-Unis. Il a obtenu une licence de l'Université du Michigan en 1961, suivie d'une maîtrise et d'un doctorat en sciences de l'Université Harvard en 1962 et 1966 respectivement. Il a commencé sa carrière d'enseignant en tant que professeur adjoint à l'Université de Californie à Berkeley en 1966. Après son départ en 1970, il a rejoint l'Université de Toronto, où il a servi dans les départements d'informatique et de mathématiques, devenant finalement professeur distingué.
Complexité de calcul
Les recherches de Cook portent principalement sur la théorie de la complexité et la complexité des démonstrations. Ses travaux novateurs sur le problème de satisfiabilité booléenne, ou SAT, ont démontré que ce problème est NP-complet, une découverte réalisée indépendamment par Leonid Levin et aujourd'hui reconnue sous le nom de théorème de Cook-Levin. Ses contributions comprennent également la définition des classes de complexité NC, SC et AC0. Au-delà de la complexité, il a étudié le calcul parallèle, la sémantique des langages de programmation et l'arithmétique bornée.
Reconnaissance professionnelle
Son travail lui a valu d'importantes distinctions internationales, notamment le prix Turing de l'ACM en 1982 pour avoir fait progresser la compréhension de la complexité de calcul. Il est membre de l'Association for Computing Machinery et de prestigieuses institutions telles que la Royal Society, la National Academy of Sciences et l'American Academy of Arts and Sciences. Au Canada, il a reçu la médaille d'or Gerhard Herzberg en sciences et en génie du Canada en 2012 et a été nommé officier de l'Ordre du Canada en 2015.
Vingt questions, huit minutes au chronomètre et un centile mesuré face à tous ceux qui l’ont passé. Sans inscription.
Passer le test de QI →En bref
- Né : 1939, Buffalo - Nationalité : Canadienne et américaine - Prix Turing : 1982 - Diplôme : Docteur en sciences - Institution académique : Université de Toronto - Distinction notable : Officier de l'Ordre du Canada - Domaine de recherche : Complexité de calcul
Questions fréquentes
### Qu'est-ce que le problème P contre NP ?
C'est une question qui demande si tout problème de décision dont les réponses peuvent être vérifiées efficacement peut également être résolu par un algorithme efficace.
### Qu'est-ce que le théorème de Cook-Levin ?
C'est la preuve formelle que le problème de satisfiabilité booléenne est NP-complet, établie indépendamment par Stephen Cook et Leonid Levin.
