Leonid Anatolievič Levin

Leonid Anatolievič Levin (; * 2. november 1948, Dnipro, Ukrajina, vtedy Ukrajinská SSR, ZSSR) je sovietsko-americký informatik a matematik. Zaoberá sa predovšetkým teoretickou informatikou - najmä výpočtovou zložitosťou, pravdepodobnostnými algoritmami a teóriou informácií.

Levin v roku 1970 vyštudoval Moskovskú štátnu univerzitu M. V. Lomonosova, kde v roku 1972 získal aj titul kandidáta vied. Jeho školiteľom bol Andrej Nikolajevič Kolmogorov. Neskôr emigroval do Spojených štátov, kde na Massachusettskom technologickom inštitúte získal v roku 1978 titul PhD. V súčasnosti pôsobí ako profesor na Bostonskej univerzite.

Leonid Levin je známy predovšetkým vďaka svojej práci v oblasti výpočtovej zložitosti. Nezávisle od Stephena Cooka v roku 1971 objavil, že SAT je NP-úplný problém, čím dokázal existenciu NP-úplných problémov. Tento výsledok je v súčasnosti známy ako Cookova-Levinova veta.

Zdroje 

 

Ukrajinskí informatici
Ruskí informatici
Informatici USA
Informatici židovského pôvodu
Ukrajinskí matematici
Ruskí matematici
Matematici USA
Matematici židovského pôvodu
Osobnosti USA židovského pôvodu
Osobnosti z Dnipra