Levin, Leonid Anatolievich

Leonid Anatolyevich Levin (narozen 2. listopadu 1948 , Dněpropetrovsk ) je sovětský a americký matematik , specialista v oblasti teorie výpočetní složitosti . Profesor informatiky na Bostonské univerzitě .

Člen Národní akademie věd USA (2019) [1] .

Životopis

Narozen 2. listopadu 1948 v Dněpropetrovsku . V roce 1970 promoval na Moskevské státní univerzitě , poté zde pracoval jako vědecký asistent pod vědeckým dohledem Andreje Kolmogorova . V roce 1971 předložil svou doktorskou práci [2] , po splnění všech formálních požadavků na její předběžné testování byla práce schválena Kolmogorovem, všemi oponenty a mateřskou organizací [3] , ale Levinovi nebyl udělen titul [4] [5] . Formálním důvodem byla „nejistota politického obrazu“ žadatele, která spolu s následnou šikanou ve vědecké komunitě sloužila jako jeden z důvodů emigrace [6] .

V letech 1972-1973 pracoval v Ústavu pro problémy přenosu informací Akademie věd SSSR a od roku 1973 do roku 1977 - ve Všesvazovém vědeckém výzkumném ústavu pro integrovanou automatizaci ropného a plynárenského průmyslu (VNIIKANeftegaz) jako vedoucí vědecký pracovník. .

V roce 1978 emigroval do USA . V roce 1979 získal titul Ph.D. v matematice na Massachusetts Institute of Technology . Od roku 1980 působí a vyučuje na Bostonské univerzitě . V roce 2014 byl zvolen členem Americké akademie umění a věd [7] .

Hlavní výsledky jsou v oblasti teorie pravděpodobnosti aplikované na informatiku, teorie výpočetní složitosti .

Nezávisle na Stephenu Cookovi dokázal v roce 1971 Cooke-Levinův teorém , díky kterému byl formulován problém rovnosti tříd P a NP , který se stal jedním z problémů tisíciletí . Práce byla publikována až v roce 1973 [8] , ale byla hlášena na konferencích, což později umožnilo stanovit Levinovu prioritu [9] .

Ocenění

• 2004 - Kolmogorovova medaile ( University of London ) [10]
• 2010 – Humboldtova cena [11]
• 2012 – Knuthova cena [12] [13]

Poznámky

1. ↑ Národní akademie věd volí členy a zahraniční členy; Historický počet žen zvolených do svého členství Archivováno 19. června 2020 na Wayback Machine 30. dubna 2019  
2. ↑ Kandidátská disertační práce L. A. Levina . Získáno 7. listopadu 2012. Archivováno z originálu dne 29. března 2017. (neurčitý)
3. ↑ Recenze na disertační práci L. A. Levina . Získáno 7. listopadu 2012. Archivováno z originálu 4. března 2016. (neurčitý)
4. ↑ B. A. Trakhtenbrot . Na památku Andrey Petrovič Ershov . Získáno 29. června 2014. Archivováno z originálu 19. června 2017. (neurčitý)
5. ↑ Rozhovor s Leonidem Levinem . Získáno 30. června 2014. Archivováno z originálu 14. října 2017. (neurčitý)
6. ↑ Cena Kutateladze S. Computer Science pro rodáka ze SSSR Archivní kopie ze dne 25. října 2016 na Wayback Machine // Trinity Option - Science . č. 23 (117) ze dne 20. listopadu 2012. S. 14.
7. ↑ Noví členové Akademie 2014 . Získáno 29. června 2014. Archivováno z originálu 19. dubna 2016. (neurčitý)
8. ↑ L. A. Levin. Univerzální enumerační  problémy // Problémy přenosu informací. - 1973. - T. 9 , č. 3 . - S. 115-116 . (Ruština)
9. ↑ Boris A. Trakhtenbrot. Přehled ruských přístupů k algoritmům Perebor (hledání hrubou silou)  //  Annals of the History of Computing. - 1984. - Sv. 6 , č. 4 . - S. 384-400 .
10. ↑ Druhá výroční Kolmogorovova přednáška archivována 5. března 2016 na Wayback Machine 
11. ↑ Leonid Levin vyhrál Humboldt Research Award Archivováno 30. května 2010 na Wayback Machine 
12. ↑ Tisková zpráva ACM, 22. srpna 2012 (odkaz není k dispozici) . Získáno 9. února 2016. Archivováno z originálu 3. března 2016. (neurčitý) 
13. ↑ Knuthova cena 2012 udělena Leonidu Levinovi . Získáno 20. listopadu 2012. Archivováno z originálu 16. ledna 2017. (neurčitý)

Literatura

• Dennis Elliott Shasha, Cathy A. Lazere. Stephen Cook a Leonid Levin: Těžko se hledá dobré řešení // Z hlavy: životy a objevy 15 skvělých počítačových vědců . - Springer, 1998. - S. 139-156. — 291 s. - (Série Koperník). — ISBN 0387982698 .

Odkazy

• Osobní stránka na  webu Bostonské univerzity . Získáno 7. listopadu 2012. Archivováno z originálu 8. května 2012.
• Životopis  . _ Získáno 7. listopadu 2012. Archivováno z originálu 8. května 2012.
• Seznam publikací  (anglicky) . Získáno 7. listopadu 2012. Archivováno z originálu 6. prosince 2012.
• Diplomová práce A. L. Levina
• Komentáře k tezi L. A. Levina

Tematické stránky	Google Scholar Matematická genealogie zbMATH Otevřeno Všeruský matematický portál
V bibliografických katalozích	ISNI : 0000 0000 2761 7298 LCCN : n87126894 VIAF : 70440154 WorldCat VIAF : 70440154