Leonid Levin - Leonid Levin

Leonid Anatolievich Levin
LeonidLevin2010.jpg
Leonid Levin 2010 -ben
Született ( 1948-11-02 )1948. november 2 (72 éves)
Dnyipropetrovszk , Ukrán Szovjetunió , Szovjetunió
alma Mater Moszkvai Egyetem,
Massachusetts Technológiai Intézet
Ismert Cook – Levin-tétel
Átlagos eset komplexitás
Bonyolultság, véletlenszerűség, információ kutatása
Díjak Knuth -díj (2012)
Tudományos karrier
Mezők matematika
Számítástechnika
Intézmények Bostoni Egyetem
Doktori tanácsadó Andrey Kolmogorov , Albert R. Meyer

Leonid Anatolievich Levin ( / l eɪ . Oʊ n i d l ɛ v ɪ n / lay-OH- NEED LEV -in ; Orosz : Леонид Анатольевич Левин ; ukrán : Леонід Анатолійович Левін ; született november 2, 1948) egy szovjet -Amerikai matematikus és informatikus .

Ő ismert, az ő munkáját véletlenszerűség a számítástechnikai , algoritmikus komplexitás és kezelhetetlen, átlagos esetben bonyolultsága , alapjait a matematika és a számítástechnika , az algoritmikus valószínűsége , elméleti számítás és információ-elmélet . A moszkvai diplomát a Moszkvai Egyetemen szerezte 1970 -ben, ahol Andrej Kolmogorov alatt tanult, és 1972 -ben elvégezte a kandidátusi fokozat követelményeit.

Ő és Stephen Cook egymástól függetlenül felfedezték az NP-teljes problémák létezését . Ez az NP-teljesség-tétel, amelyet gyakran Cook-Levin-tételnek is neveznek , alapja volt a hét Milleniumi Díjprobléma egyikének, amelyet az Agyag Matematikai Intézet hirdetett meg 1 000 000 dolláros díjjal. A Cook -Levin -tétel áttörést jelentett az informatikában, és fontos lépést tett a számítási komplexitás elméletének fejlődésében .

Levin 2012 - ben Knuth-díjat kapott az NP-teljesség felfedezéséért és az átlagos esetek összetettségének fejlesztéséért . Az Egyesült Államok Nemzeti Tudományos Akadémiájának tagja és az Amerikai Művészeti és Tudományos Akadémia tagja .

Életrajz

A moszkvai diplomát a Moszkvai Egyetemen szerezte 1970 -ben, ahol Andrej Kolmogorov alatt tanult, és 1972 -ben elvégezte a kandidátusi fokozat követelményeit. Miután 1972–1973 -ban 1972–1973 között a Nemzeti Tudományos Akadémia moszkvai információátviteli intézetében kutatta az információelmélet algoritmikus problémáit. , és 1973–1977 között a moszkvai Nemzeti Olaj- és Gázipari Automatizálási Kutatóintézet tudományos főmunkatársa volt , 1978 -ban emigrált az Egyesült Államokba , és doktori címet is szerzett. 1979 -ben a Massachusettsi Technológiai Intézetben (MIT). Tanácsadója az MIT -ben Albert R. Meyer volt .

Ő jól ismert munkája a véletlenszerűség a számítástechnikai , algoritmikus komplexitás és kezelhetetlen, átlagos esetben bonyolultsága , alapjait a matematika és a számítástechnika , az algoritmikus valószínűsége , elméleti számítás és információ-elmélet .

Életét az Elméjükből: 15 nagy számítástechnikus élete és felfedezése című könyv egyik fejezete írja le .

Levin és Stephen Cook önállóan fedezték fel az NP-teljes problémák létezését . Ez az NP-teljesség-tétel, amelyet gyakran Cook-Levin-tételnek is neveznek , alapja volt a hét Milleniumi Díjprobléma egyikének, amelyet az Agyag Matematikai Intézet hirdetett meg 1 000 000 dolláros díjjal. A Cook – Levin -tétel áttörést jelentett az informatikában, és fontos lépést tett a számítási komplexitás elméletének fejlődésében . Levin folyóiratcikke erről a tételről 1973 -ban jelent meg; ezt megelőzően néhány évig előadásokat tartott a benne található ötletekről (lásd Trakhtenbrot felmérését), bár az eredmények teljes formális megírása Cook közzététele után történt.

Levin 2012 - ben Knuth-díjat kapott az NP-teljesség felfedezéséért és az átlagos esetek összetettségének fejlesztéséért .

Jelenleg a Bostoni Egyetem informatikai professzora , ahol 1980 -ban kezdett tanítani.

Megjegyzések

Hivatkozások

Külső linkek