Leonid Levin

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

Leonid Anatolievich Levin

Description de cette image, également commentée ci-après

Leonid Levin en 2010

Renommé pour Théorème de Cook-Levin

Leonid Anatolievich Levin (russe : Леонид Анатольевич Левин, né le 2 novembre 1948 à Dnipropetrovsk, RSS d'Ukraine) est un informaticien russo-ukraino-américain. Il est connu notamment pour avoir découvert la notion de NP-complétude en même temps que Stephen Cook.

Biographie[modifier | modifier le code]

Il obtient son master en 1970 et l'équivalent du doctorat en 1972 à l'université de Moscou sous la direction d'Andreï Kolmogorov. En 1978, il émigre aux États-Unis et obtient également un doctorat au Massachusetts Institute of Technology en 1979. Son directeur de thèse au MIT est Albert Meyer.

Il est connu pour son travail sur le hasard en informatique, la complexité algorithmique, la complexité en moyenne des algorithmes[1], la probabilité algorithmique, la théorie de la calculabilité et la théorie de l'information.

Sa vie est décrite dans un chapitre du livre Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists[2].

Levin a découvert indépendamment de Stephen Cook le théorème central de la NP-complétude, qu'on nomme aujourd'hui théorème de Cook-Levin. Ce théorème est lié au problème P = NP, l'un des sept problèmes du prix du millénaire pour lesquels l'Institut Clay offre un prix d'un million de dollars. C'est une découverte majeure de l'informatique théorique et le fondement de la théorie de la complexité. L'article de Levin est publié en 1973, mais il en avait présenté les idées lors de ses enseignements quelques années auparavant (voir l'étude de Trakhtenbrot[3]), bien que l'écriture complète et formelle des résultats soit postérieure à la publication du résultat de Cook.

Il est actuellement professeur d'informatique à l'université de Boston, où il enseigne depuis 1980.

Notes et références[modifier | modifier le code]

  1. Leonid Levin. Average-case complete problems. SIAM J. Comput., 15:285–286, 1986.
  2. Shasha, Dennis; Cathy Lazere (September 1995). Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. Springer. ISBN 0-387-97992-1.
  3. Boris A. Trakhtenbrot (1984). "A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms". Annals of the History of Computing (IEEE) 6 (4): 384–400.

Lien externe[modifier | modifier le code]

(en) Page personnelle de Leonid Levin