Juris Hartmanis

Article

August 17, 2022

Juris Hartmanis (5 juli 1928 – 29 juli 2022) var en lettisk-född amerikansk datavetare och beräkningsteoretiker som tillsammans med Richard E. Stearns fick ACM Turing Award 1993 "som ett erkännande för deras framstående artikel som lade grunden för fältet beräkningskomplexitetsteori".

Liv och karriär

Hartmanis föddes i Lettland den 5 juli 1928. Han var son till Mārtiņš Hartmanis, en general i den lettiska armén, och bror till poeten Astrid Ivask. Efter att Sovjetunionen ockuperade Lettland 1940 arresterades Mārtiņš Hartmanis av sovjeterna och dog i ett fängelse. Senare under andra världskriget lämnade Mārtiņš Hartmanis fru och barn Lettland 1944 som flyktingar, av rädsla för deras säkerhet om Sovjetunionen skulle ta över Lettland igen. De flyttade först till Tyskland, där Juris Hartmanis fick motsvarande en magisterexamen i fysik från universitetet i Marburg. Han flyttade sedan till USA, där han 1951 fick en magisterexamen i tillämpad matematik vid University of Kansas City (nu känt som University of Missouri–Kansas City) och 1955 en Ph.D. i matematik från Caltech under ledning av Robert P. Dilworth. University of Missouri-Kansas City hedrade honom med en hedersdoktor i humanistiska brev i maj 1999. Efter att ha undervisat i matematik vid Cornell University och Ohio State University, gick Hartmanis med i General Electric Research Laboratory 1958. Medan han var på General Electric utvecklade han många principer för beräkningskomplexitetsteori. 1965 blev han professor vid Cornell University. Han var en av grundarna och den första ordföranden för dess datavetenskapsavdelning (som var en av de första datavetenskapliga institutionerna i världen). Hartmanis bidrog till nationella ansträngningar för att främja datavetenskap och ingenjörsvetenskap (CS&E) på många sätt. Det viktigaste är att han var ordförande för National Research Council-studien som resulterade i 1992 års publikation Computing the Future – A Broad Agenda for Computer Science and Engineering, som gav rekommendationer baserade på dess prioriteringar för att upprätthålla kärnansträngningen inom CS&E, för att bredda fältet, och att förbättra grundutbildningen i CS&E. Han var biträdande direktör för National Science Foundation (NSF) Directorate of Computer and Information Science and Engineering (CISE) från 1996 till 1998. 1989 valdes Hartmanis in som medlem i National Academy of Engineering för grundläggande bidrag till beräkningskomplexitetsteori och till forskning och utbildning inom datoranvändning. Han var medlem i Association for Computing Machinery och American Mathematical Society, även medlem av National Academy of Sciences. Han var också en utländsk medlem av den lettiska vetenskapsakademin, som gav honom deras stora medalj 2001 för hans bidrag till datavetenskap. Hartmanis dog den 29 juli 2022.

Beräkningskomplexitet: grundläggande bidrag

1993 gjorde Hartmanis och R.E. Stearns tog emot det högsta priset i datavetenskap, Turing Award. Citatet lyder, "Som ett erkännande för deras nyskapande papper som lade grunden för fältet av beräkningskomplexitetsteorin." Deras papper definierade den grundläggande föreställningen om en komplexitetsklass, ett sätt att klassificera beräkningsproblem efter den tid som krävs för att lösa dem. De fortsatte med att bevisa ett antal grundläggande resultat såsom Tidshierarkisats. I sin egen Turing Award-föreläsning påpekar Richard M. Karp att "[I]t is the 1965 paper by Juris Hartmanis and Richard Stearns that marks the beginning of the modern era of komplexitetsteori." Med P.M. Lewis II definierade Hartmanis och Stearns också komplexitetsklasser baserade på utrymmesanvändning och bevisade den första rymdhierarkisatsen. Samma år de bevisade också att alla sammanhangsfria språk har deterministiska rymdkomplexitet (log n)2, som innehöll den väsentliga idé som ledde till Savitchs teorem om rymdkomplexitet. Hartmanis fortsatte att göra signi