Juris Hartmanis

Article

August 17, 2022

Juris Hartmanis (5 juli 1928 - 29 juli 2022) was een in Letland geboren Amerikaanse computerwetenschapper en computationeel theoreticus die samen met Richard E. Stearns de 1993 ACM Turing Award ontving "als erkenning voor hun baanbrekende artikel dat de basis legde voor het gebied van computationele complexiteitstheorie".

Leven en carrière

Hartmanis werd geboren in Letland op 5 juli 1928. Hij was een zoon van Mārtiņš Hartmanis, een generaal in het Letse leger, en broer van de dichter Astrid Ivask. Nadat de Sovjet-Unie Letland in 1940 bezette, werd Mārtiņš Hartmanis gearresteerd door de Sovjets en stierf in een gevangenis. Later in de Tweede Wereldoorlog verlieten de vrouw en kinderen van Mārtiņš Hartmanis Letland in 1944 als vluchteling, uit angst voor hun veiligheid als de Sovjet-Unie Letland weer zou overnemen. Ze verhuisden eerst naar Duitsland, waar Juris Hartmanis het equivalent van een masterdiploma in natuurkunde van de Universiteit van Marburg. Daarna verhuisde hij naar de Verenigde Staten, waar hij in 1951 een master's degree in toegepaste wiskunde behaalde aan de University of Kansas City (nu bekend als de University of Missouri-Kansas City) en in 1955 een Ph.D. in wiskunde van Caltech onder toezicht van Robert P. Dilworth. De Universiteit van Missouri-Kansas City eerde hem in mei 1999 met een eredoctoraat in Humane Letters. Nadat hij wiskunde had gedoceerd aan de Cornell University en de Ohio State University, trad Hartmanis in 1958 toe tot het General Electric Research Laboratory. Bij General Electric ontwikkelde hij veel principes van computationele complexiteitstheorie. In 1965 werd hij professor aan de Cornell University. Hij was een van de oprichters en de eerste voorzitter van de informatica-afdeling (die een van de eerste informatica-afdelingen ter wereld was). Hartmanis heeft op vele manieren bijgedragen aan de nationale inspanningen om de computerwetenschap en -techniek (CS&E) te bevorderen. Het belangrijkste was dat hij voorzitter was van de studie van de National Research Council die resulteerde in de publicatie Computing the Future - A Broad Agenda for Computer Science and Engineering uit 1992, waarin aanbevelingen werden gedaan op basis van de prioriteiten om de kerninspanning in CS&E te ondersteunen, het veld te verbreden, en om het lager onderwijs in CS&E te verbeteren. Hij was adjunct-directeur van de National Science Foundation (NSF) Directorate of Computer and Information Science and Engineering (CISE) van 1996 tot 1998. In 1989 werd Hartmanis verkozen als lid van de National Academy of Engineering voor fundamentele bijdragen aan de computationele complexiteitstheorie en aan onderzoek en onderwijs in informatica. Hij was een Fellow van de Association for Computing Machinery en van de American Mathematical Society, ook lid van de National Academy of Sciences. Hij was ook een buitenlands lid van de Letse Academie van Wetenschappen, die hem in 2001 hun Grote Medaille schonken voor zijn bijdragen aan de informatica. Hartmanis stierf op 29 juli 2022.

Computationele complexiteit: fundamentele bijdragen

In 1993 hebben Hartmanis en R.E. Stearns ontvangen de hoogste prijs in de informatica, de Turing Award. Het citaat luidt, "Als erkenning voor hun baanbrekende papier dat de basis legde voor het veld van computationele complexiteitstheorie." hun papier definieerde het fundamentele begrip van een klasse Complexiteit, een manier om het classificeren van computationele problemen volgens de tijd die nodig is om ze op te lossen. Ze gingen verder met het bewijzen van een aantal fundamentele resultaten, zoals de Tijdhiërarchie stelling. In zijn eigen Turing Award-lezing merkt Richard M. Karp op: "[I]t is the 1965 paper by Juris Hartmanis and Richard Stearns that markeert het begin van het moderne tijdperk van complexiteitstheorie." Met P.M. Lewis II definieerden Hartmanis en Stearns ook complexiteitsklassen op basis van ruimtegebruik en bewezen de eerste ruimtehiërarchiestelling. In hetzelfde jaar hebben ze bewees ook dat elke contextvrije taal deterministische ruimtecomplexiteit (log n)2, die het essentiële idee bevatte dat leidde tot aan de stelling van Savitch over ruimtecomplexiteit. Hartmanis bleef signi