Leonid Levin

Leonid Anatolievič Levin (* 2. listopad 1948, Dnipro, Ukrajina, tehdy Ukrajinská SSR, SSSR) je ukrajinsko-americký informatik a matematik. Zabývá se především teoretickou informatikou - především výpočetní složitostí, pravděpodobnostními algoritmy a teorií informace.

Levin v roce 1970 vystudoval Moskovskou státní univerzitu M. V. +more Lomonosova, kde v roce 1972 získal i titul kandidáta věd. Jeho školitelům byl Andrej Nikolajevič Kolmogorov. Později emigroval do Spojených států, kde v roce 1978 získal titul PhD. na MIT. V současnosti působí jako profesor na Bostonské univerzitě.

Leonid Levin je znám především díky své práci v oblasti výpočetní složitosti. Nezávisle na Stephenu Cookovi V roce 1971 objevil, že problém splnitelnosti booleovské formulí (SAT) je NP-úplný, čímž dokázal existenci NP-úplných problémů. +more Tento výsledek je v současnosti znám jako Cookova-Levinova věta.

Reference

Externí odkazy

Kategorie:Američtí informatici Kategorie:Židovští informatici Kategorie:Ukrajinští matematici Kategorie:Ruští matematici Kategorie:Američtí matematici Kategorie:Židovští matematici Kategorie:Američtí Židé Kategorie:Osobnosti z Dnipra