Juris Hartmanis

Article

August 19, 2022

Juris Hartmanis (5. Juli 1928 - 29. Juli 2022) war ein in Lettland geborener amerikanischer Informatiker und Computertheoretiker, der zusammen mit Richard E. Stearns 1993 den ACM Turing Award "in Anerkennung ihrer wegweisenden Arbeit erhielt, die die Grundlagen für dem Gebiet der Computational Complexity Theory".

Leben und Karriere

Hartmanis wurde am 5. Juli 1928 in Lettland geboren. Er war ein Sohn von Mārtiņš Hartmanis, einem General der lettischen Armee, und Bruder der Dichterin Astrid Ivask. Nachdem die Sowjetunion 1940 Lettland besetzt hatte, wurde Mārtiņš Hartmanis von den Sowjets festgenommen und starb in einem Gefängnis. Später im Zweiten Weltkrieg verließen die Frau und die Kinder von Mārtiņš Hartmanis Lettland im Jahr 1944 als Flüchtlinge aus Angst um ihre Sicherheit, falls die Sowjetunion Lettland erneut übernehmen sollte. Sie zogen zunächst nach Deutschland, wo Juris Hartmanis das Äquivalent eines Master-Abschlusses erhielt Physik an der Universität Marburg. Anschließend zog er in die Vereinigten Staaten, wo er 1951 einen Master-Abschluss in angewandter Mathematik an der University of Kansas City (heute bekannt als University of Missouri-Kansas City) und 1955 einen Ph.D. in Mathematik vom Caltech unter der Leitung von Robert P. Dilworth. Die University of Missouri-Kansas City ehrte ihn im Mai 1999 mit einem Ehrendoktor für Humane Letters. Nachdem er Mathematik an der Cornell University und der Ohio State University unterrichtet hatte, trat Hartmanis 1958 dem General Electric Research Laboratory bei. Während seiner Zeit bei General Electric entwickelte er viele Prinzipien der Computational Complexity Theory. 1965 wurde er Professor an der Cornell University. Er war einer der Gründer und der erste Vorsitzende der Informatikabteilung (eine der ersten Informatikabteilungen der Welt). Hartmanis trug in vielerlei Hinsicht zu den nationalen Bemühungen zur Förderung der Informatik und des Ingenieurwesens (CS&E) bei. Vor allem leitete er die Studie des National Research Council, die 1992 zu der Veröffentlichung Computing the Future – A Broad Agenda for Computer Science and Engineering führte, die auf der Grundlage ihrer Prioritäten Empfehlungen aussprach, um die Kernanstrengungen in CS&E aufrechtzuerhalten, das Feld zu erweitern und um die Grundausbildung in CS&E zu verbessern. Von 1996 bis 1998 war er stellvertretender Direktor der National Science Foundation (NSF) Directorate of Computer and Information Science and Engineering (CISE). 1989 wurde Hartmanis als Mitglied in die National Academy of Engineering für grundlegende Beiträge zur Computational Complexity Theory und zur Forschung und Ausbildung im Computerbereich gewählt. Er war Fellow der Association for Computing Machinery und der American Mathematical Society sowie Mitglied der National Academy of Sciences. Er war auch ausländisches Mitglied der Lettischen Akademie der Wissenschaften, die ihm 2001 ihre Große Medaille für seine Verdienste um die Informatik verlieh. Hartmanis starb am 29. Juli 2022.

Rechenkomplexität: grundlegende Beiträge

1993 Hartmanis und R.E. Stearns erhalten der höchste Preis in der Informatik, der Turing Award. Das Zitat lautet, "In Anerkennung ihrer bahnbrechenden Arbeit, die die Grundlagen für das Gebiet gelegt hat der Computational Complexity Theory." Ihr Papier definierte den grundlegenden Begriff einer Komplexitätsklasse, einen Weg von Rechenprobleme nach der für ihre Lösung erforderlichen Zeit zu klassifizieren. Sie fuhren fort, eine Reihe grundlegender Ergebnisse zu beweisen, wie z Theorem der Zeithierarchie. In seiner eigenen Turing-Award-Vorlesung bemerkt Richard M. Karp: „[I]t es die Arbeit von Juris Hartmanis und Richard Stearns aus dem Jahr 1965, die den Beginn der modernen Ära der Komplexitätstheorie.“ Mit P.M. Lewis II haben Hartmanis und Stearns auch Komplexitätsklassen basierend auf der Raumnutzung definiert und bewiesen der erste Satz der Raumhierarchie. Im selben Jahr sie bewies auch, dass jede kontextfreie Sprache deterministisch ist Raumkomplexität (log n)2, die die wesentliche Idee enthielt, die dazu führte zum Satz von Savitch über die Raumkomplexität. Hartmanis machte weiterhin Zeichen