Le théorème de Cook-Levin fournit un cadre fondamental pour comprendre la complexité theorique, marquant un moment charnière de l'informatique du XXe siècle. Développé indépendamment par Leonid Levin et Stephen Cook, cet apport a établi l'existence des problèmes NP-complets, créant de fait une base de référence pour évaluer la difficulté des tâches mathématiques qui sous-tendent l'infrastructure numérique moderne et l'efficacité algorithmique.
Fondements académiques en Union soviétique
Né en 1948 à Dnipro, Levin a suivi une formation mathématique rigoureuse au sein du système soviétique. Il a fréquenté l'Université d'État Lomonossov de Moscou, y obtenant sa maîtrise en 1970 sous la direction d'Andreï Kolmogorov. Dès 1972, il avait rempli les conditions requises pour obtenir un diplôme de candidat ès sciences. Durant cette première période, il s'est intéressé à la théorie de l'information à l'Institut de transmission de l'information de l'Académie des sciences de Moscou. Entre 1973 et 1977, il a exercé les fonctions de chercheur scientifique senior à l'Institut de recherche national de Moscou pour l'automatisation intégrée de l'industrie pétrolière et gazière.
Transition vers les États-Unis et le MIT
Levin a émigré aux États-Unis en 1978 pour poursuivre ses recherches. Il s'est inscrit au Massachusetts Institute of Technology, où il a obtenu un doctorat (Ph.D.) en 1979 sous la supervision d'Albert R. Meyer. Peu après, en 1980, il a rejoint le corps professoral de l'Université de Boston, où il exerce toujours en tant que professeur d'informatique. Ses travaux se sont largement concentrés sur la théorie des probabilités, l'informatique et les fondements profonds du calcul.
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 →Contributions scientifiques et reconnaissance
Contributions scientifiques et reconnaissance
En bref
- Naissance : 1948, Dnipro - Nationalité : États-Unis, Union soviétique - Directeur de thèse : Albert R. Meyer - Employeur : Université de Boston - Prix Knuth : 2012 - Prix Humboldt : 2010 - Bourse Guggenheim : 1993
Questions des lecteurs
### Qu'est-ce que le théorème de Cook-Levin ?
C'est un théorème fondamental en informatique qui identifie l'existence des problèmes NP-complets, décrivant ainsi les limites de la complexité algorithmique.
### Où Leonid Levin enseigne-t-il ?
Il est professeur d'informatique à l'Université de Boston, où il occupe un poste depuis 1980.
