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. Lomonosova, kde v roce 1972 získal i titul kandidáta věd. Jeho školitelem 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ů. 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