Leonid Levin

Leonid Anatolievich Levin
LeonidLevin2010.jpg
Leonid Levin im Jahr 2010
Geboren 2. November 1948 (Alter 73)
Dnipropetrovsk, Ukrainischer SSR, Sovietunion
Alma Mater Moskauer Universität
Massachusetts Institute of Technology
Bekannt für Cook -Levin -Theorem
Durchschnittsfallkomplexität
Forschung in Komplexität, Zufälligkeit, Informationen
Auszeichnungen Knuth -Preis (2012)
Wissenschaftliche Karriere
Felder Mathematik
Informatik
Institutionen Boston Universität
Doktorand Andrey Kolmogorov, Albert R. Meyer

Leonid Anatolievich Levin (/leɪ.oʊˈnichd ˈlɛvɪn/ Lay-oh-BRAUCHEN Lev-in; Russisch: Леони́д Анато́льевич Ле́вин; ukrainisch: Леоні́д Анато́лійович Ле́він; Geboren am 2. November 1948) ist ein sowjetisch-amerikanischer Fall Mathematiker und Informatiker.

Er ist bekannt für seine Arbeit in Zufälligkeit in Computer, Algorithmische Komplexität und Uneinheitlichkeit, Durchschnittsfallkomplexität,[1] Fundamente von Mathematik und Informatik, Algorithmische Wahrscheinlichkeit, Theorie der Berechnung, und Informationstheorie. Er erhielt seinen Master -Abschluss bei Moskauer Universität 1970, wo er unter studierte Andrey Kolmogorov und absolvierte die Kandidatenabschluss Akademische Anforderungen im Jahr 1972.[2]

Er und Stephen Cook unabhängig entdeckt die Existenz von NP-Complete-Probleme. Dieser NP-Completness-Theorem, oft als das genannt Cook -Levin -Theoremwar eine Grundlage für eine der sieben Millennium Prize Problems deklariert durch die Clay Mathematics Institute mit einem Preis von 1.000.000 US -Dollar. Der Koch -Levin -Theorem war ein Durchbruch in Informatik und ein wichtiger Schritt in der Entwicklung der Theorie von Rechenkomplexität.

Levin wurde mit dem ausgezeichnet Knuth -Preis in 2012[3] für seine Entdeckung der NP-Vervollständigung und der Entwicklung von Durchschnittsfallkomplexität. Er ist Mitglied der USA Nationale Akademie der Wissenschaften und ein Stipendiat der Amerikanische Akademie für Kunst und Wissenschaften.

Biografie

Er erhielt seinen Master -Abschluss bei Moskauer Universität 1970, wo er unter studierte Andrey Kolmogorov und absolvierte die Kandidatenabschluss Akademische Anforderungen im Jahr 1972.[2][4] Nach der Untersuchung algorithmischer Probleme der Informationstheorie am Moskauer Institut für Informationsübertragung der Nationale Akademie der Wissenschaften 1972–1973 und eine Position als leitender Forschungswissenschaftler am Moskauer National Research Institute für integrierte Automatisierung für die Öl-/Gasindustrie 1973–1977 wanderte er in die aus UNS. 1978 und erwarb auch einen Ph.D. Bei der Massachusetts Institute of Technology (MIT) 1979.[2] Sein Berater am MIT war Albert R. Meyer.

Er ist bekannt für seine Arbeit in Zufälligkeit in Computer, Algorithmische Komplexität und Uneinheitlichkeit, Durchschnittsfallkomplexität,[1] Fundamente von Mathematik und Informatik, Algorithmische Wahrscheinlichkeit, Theorie der Berechnung, und Informationstheorie.

Sein Leben wird in einem Kapitel des Buches beschrieben Aus ihren Köpfen: Das Leben und Entdeckungen von 15 großen Informatikern.[5]

Levin und Stephen Cook unabhängig entdeckt die Existenz von NP-Complete-Probleme. Dieser NP-Completness-Theorem, oft als das genannt Cook -Levin -Theoremwar eine Grundlage für eine der sieben Millennium Prize Problems deklariert durch die Clay Mathematics Institute mit einem Preis von 1.000.000 US -Dollar. Der Koch -Levin -Theorem war ein Durchbruch in Informatik und ein wichtiger Schritt in der Entwicklung der Theorie von Rechenkomplexität. Levins Journal -Artikel über diesen Theorem wurde 1973 veröffentlicht.[6] Er hatte einige Jahre vor dieser Zeit über die Ideen gehandelt (siehe TrakhtenbrotSurvey),[7] Obwohl das vollständige formelle Schreiben der Ergebnisse nach der Veröffentlichung von Cook stattfand.

Levin wurde mit dem ausgezeichnet Knuth -Preis in 2012[3] für seine Entdeckung der NP-Vervollständigung und der Entwicklung von Durchschnittsfallkomplexität.

Er ist derzeit Professor für Informatik bei Boston Universität, wo er 1980 unterrichtete.

Anmerkungen

  1. ^ a b Levin, Leonid (1986). "Durchschnittlich vollständige Probleme". Siam J. Comput. 15 (1): 285–6. doi:10.1137/0215020.
  2. ^ a b c Levins Curriculum Fritae
  3. ^ a b ACM -Pressemitteilung, 22. August 2012 Archiviert 3. März 2016 bei der Wayback -Maschine
  4. ^ 1971 Dissertation (auf Russisch); englische Übersetzung bei Arxiv
  5. ^ Shasha, Dennis; Cathy Lazere (September 1995). Aus ihren Köpfen: Das Leben und Entdeckungen von 15 großen Informatikern. Springer. ISBN 0-387-97992-1.
  6. ^ Levin, Leonid (1973). "Universelle Suchprobleme (Russisch: универсальные задачи перебора, universell'nye perebornye zadachi)". Probleme der Informationsübertragung (Russian: проблеgst передачи ches фор & мbehT, problemy Peredachi Informatii). 9 (3): 115–116. (PDF)
  7. ^ Boris A. Trakhtenbrot (1984). "Eine Übersicht über russische Ansätze zu Perebor (Brute-Force-Suchanfragen) Algorithmen". Annalen der Geschichte des Computers. IEEE. 6 (4): 384–400. doi:10.1109/mahc.1984.10036. S2CID 950581.

Verweise

Externe Links