Der Satz von Cook und Levin bildet einen grundlegenden Rahmen zum Verständnis der Rechenkomplexität und markiert einen Wendepunkt in der Informatik des 20. Jahrhunderts. Diese unabhängig voneinander von Leonid Levin und Stephen Cook entwickelte Erkenntnis etablierte die Existenz von NP-vollständigen Problemen und schuf damit eine Basis zur Bewertung der Schwierigkeit mathematischer Aufgaben, die die moderne digitale Infrastruktur und algorithmische Effizienz stützen.
Akademische Grundlagen in der Sowjetunion
Levin wurde 1948 in Dnipro geboren und absolvierte eine streng mathematische Ausbildung im sowjetischen System. Er studierte an der Lomonossow-Universität Moskau und schloss sein Masterstudium 1970 unter der Betreuung von Andrei Kolmogorow ab. Bis 1972 hatte er die Anforderungen für einen Kandidatengrad erfüllt. In dieser frühen Phase beschäftigte er sich mit Informationstheorie am Institut für Informationsübertragung der Akademie der Wissenschaften in Moskau. Zwischen 1973 und 1977 war er als leitender wissenschaftlicher Mitarbeiter am Moskauer Forschungsinstitut für integrierte Automatisierung der Öl- und Gasindustrie tätig.
Übergang in die Vereinigten Staaten und ans MIT
Levin emigrierte 1978 in die Vereinigten Staaten, um seine Forschung fortzusetzen. Er schrieb sich am Massachusetts Institute of Technology ein, wo er 1979 unter der Betreuung von Albert R. Meyer promovierte. Kurz darauf, im Jahr 1980, wurde er Dozent an der Boston University, wo er bis heute als Professor für Informatik tätig ist. Seine Arbeit konzentriert sich stark auf Wahrscheinlichkeitstheorie, Informatik und die tieferen Grundlagen der Berechenbarkeit.
Wissenschaftliche Beiträge und Anerkennung
Über seine Grundlagenarbeit zur NP-Vollständigkeit hinaus hat Levin die Forschung zur Zufälligkeit in der Informatik und zur Komplexität im Durchschnittsfall maßgeblich vorangetrieben. Seine Beiträge wurden durch mehrere renommierte Ehrungen gewürdigt, darunter ein Guggenheim-Stipendium (1993), der Humboldt-Forschungspreis (2010) und der Knuth-Preis (2012). Er ist Mitglied der National Academy of Sciences und der American Academy of Arts and Sciences.
Zwanzig Fragen, acht Minuten auf der Uhr und ein Perzentil, gemessen an allen bisherigen Teilnehmern. Ohne Anmeldung.
IQ-Test starten →Steckbrief
- Geboren: 1948, Dnipro - Staatsbürgerschaft: Vereinigte Staaten, Sowjetunion - Doktorvater: Albert R. Meyer - Arbeitgeber: Boston University - Knuth-Preis: 2012 - Humboldt-Preis: 2010 - Guggenheim-Stipendium: 1993
Häufig gestellte Fragen
### Was ist der Satz von Cook und Levin?
Es ist ein grundlegender Satz der Informatik, der die Existenz von NP-vollständigen Problemen aufzeigt und die Grenzen der Rechenkomplexität beschreibt.
### Wo lehrt Leonid Levin?
Er ist Professor für Informatik an der Boston University, wo er seit 1980 eine Professur innehat.
