Levin, Leonyid Anatoljevics

Leonyid Anatoljevics Levin ( 1948. november 2., Dnyipropetrovszk ) szovjet és amerikai matematikus , a számítási komplexitás -elmélet szakértője . Számítástechnika professzor a Bostoni Egyetemen .

Az Egyesült Államok Nemzeti Tudományos Akadémiájának tagja (2019) [1] .

Életrajz

1948. november 2- án született Dnyipropetrovszkban . 1970-ben diplomázott a Moszkvai Állami Egyetemen , majd ott dolgozott kutatási asszisztensként Andrej Kolmogorov tudományos felügyelete mellett . 1971-ben bemutatta Ph.D. értekezését [2] , az előzetes teszteléshez szükséges összes formai követelmény teljesítése után a dolgozatot Kolmogorov, valamennyi opponens és az anyaszervezet jóváhagyta [3] , de Levin nem kapott diplomát [4] [5] . Ennek formális oka a kérelmező „politikai imázsának bizonytalansága” volt, amely a tudományos közösségben bekövetkezett későbbi zaklatással együtt a kivándorlás egyik okaként szolgált [6] .

1972-1973 között a Szovjetunió Tudományos Akadémia Információátviteli Problémái Intézetében , 1973-tól 1977-ig az Össz-Unioni Olaj- és Gázipari Integrált Automatizálási Tudományos Kutatóintézetben (VNIIKANeftegaz) dolgozott tudományos főmunkatársként. .

1978-ban emigrált az USA -ba . 1979-ben szerzett Ph.D. fokozatot matematikából a Massachusetts Institute of Technology -n . 1980 óta a Bostoni Egyetemen dolgozik és tanít . 2014-ben az Amerikai Művészeti és Tudományos Akadémia tagjává választották [7] .

A fő eredmények a számítástechnikában alkalmazott valószínűségszámítás , a számítási komplexitás elmélete területén vannak .

Stephen Cooktól függetlenül 1971-ben bebizonyította a Cooke-Levin tételt , melynek köszönhetően megfogalmazódott a P és NP osztályok egyenlőségének problémája , amely az ezredforduló egyik problémája lett . A mű csak 1973-ban jelent meg [8] , de konferenciákon beszámoltak róla, ami később lehetővé tette Levin prioritásának megállapítását [9] .

Díjak

• 2004 – Kolmogorov-érem ( Londoni Egyetem ) [10]
• 2010 – Humboldt-díj [11]
• 2012 – Knuth-díj [12] [13]

Jegyzetek

1. ↑ A Nemzeti Tudományos Akadémia tagokat és külföldi munkatársakat választ; A tagságba megválasztott nők történelmi száma archiválva 2020. június 19-én a Wayback Machine -nél 2019.   április 30 .
2. ↑ L. A. Levin kandidátusi disszertációja . Letöltve: 2012. november 7. Az eredetiből archiválva : 2017. március 29. (határozatlan)
3. ↑ Vélemények L. A. Levin disszertációjáról . Letöltve: 2012. november 7. Az eredetiből archiválva : 2016. március 4.. (határozatlan)
4. ↑ B. A. Trakhtenbrot . Andrej Petrovics Ershov emlékére . Letöltve: 2014. június 29. Az eredetiből archiválva : 2017. június 19. (határozatlan)
5. ↑ Interjú Leonid Levinnel . Letöltve: 2014. június 30. Az eredetiből archiválva : 2017. október 14.. (határozatlan)
6. ↑ Kutateladze S. Számítástechnikai Díj a Szovjetunió szülöttének 2016. október 25-i archív példány a Wayback Machine -nél // Trinity Option - Science . 23. szám (117) 2012. november 20. 14. o.
7. ↑ Az új 2014-es akadémiai tagok . Letöltve: 2014. június 29. Az eredetiből archiválva : 2016. április 19.. (határozatlan)
8. ↑ L. A. Levin. Univerzális felsorolási  problémák // Az információtovábbítás problémái. - 1973. - T. 9 , 3. sz . - S. 115-116 . (Orosz)
9. ↑ Boris A. Trakhtenbrot. A Perebor (Brute-Force Search) algoritmusok orosz megközelítéseinek felmérése  //  Annals of the History of Computing. - 1984. - 1. évf. 6 , sz. 4 . - P. 384-400 .
10. ↑ Második éves Kolmogorov-előadás archiválva 2016. március 5-én a Wayback Machine -nél 
11. ↑ Leonid Levin elnyerte a Humboldt kutatási díjat . Archiválva : 2010. május 30. a Wayback Machine -nél 
12. ↑ ACM sajtóközlemény, 2012. augusztus 22. (a hivatkozás nem elérhető) . Letöltve: 2016. február 9. Az eredetiből archiválva : 2016. március 3. (határozatlan) 
13. ↑ A 2012-es Knuth-díjat Leonid Levin kapta . Letöltve: 2012. november 20. Az eredetiből archiválva : 2017. január 16.. (határozatlan)

Irodalom

• Dennis Elliott Shasha, Cathy A. Lazere. Stephen Cook és Leonid Levin: Nehéz jó megoldást találni // Elment az eszük: 15 nagyszerű informatikus élete és felfedezései . - Springer, 1998. - S. 139-156. — 291 p. - (Kopernikusz sorozat). — ISBN 0387982698 .

Linkek

• Személyes oldal a Bostoni Egyetem  honlapján . Letöltve: 2012. november 7. Az eredetiből archiválva : 2012. május 8..
• Önéletrajz  . _ Letöltve: 2012. november 7. Az eredetiből archiválva : 2012. május 8..
• Publikációk listája  (angol) . Letöltve: 2012. november 7. Az eredetiből archiválva : 2012. december 6..
• A. L. Levin szakdolgozata
• Megjegyzések L. A. Levin téziséhez

Tematikus oldalak	Google ösztöndíjas Matematikai genealógia zbMATH Nyitva Össz-orosz matematikai portál
Bibliográfiai katalógusokban	ISNI : 0000 0000 2761 7298 LCCN : n87126894 VIAF : 70440154 WorldCat VIAF : 70440154