Juris Hartmanis

Article

August 16, 2022

Juris Hartmanis (5 de julho de 1928 - 29 de julho de 2022) foi um cientista da computação e teórico computacional americano nascido na Letônia que, com Richard E. Stearns, recebeu o Prêmio ACM Turing de 1993 "em reconhecimento ao seu artigo seminal que estabeleceu as bases para o campo da teoria da complexidade computacional".

Vida e carreira

Hartmanis nasceu na Letônia em 5 de julho de 1928. Era filho de Mārtiņš Hartmanis, general do exército letão e irmão da poetisa Astrid Ivask. Depois que a União Soviética ocupou a Letônia em 1940, Mārtiņš Hartmanis foi preso pelos soviéticos e morreu em uma prisão. Mais tarde, na Segunda Guerra Mundial, a esposa e os filhos de Mārtiņš Hartmanis deixaram a Letônia em 1944 como refugiados, temendo por sua segurança se a União Soviética tomasse a Letônia novamente. Eles se mudaram primeiro para a Alemanha, onde Juris Hartmanis recebeu o equivalente a um mestrado em física da Universidade de Marburg. Ele então se mudou para os Estados Unidos, onde em 1951 recebeu um mestrado em matemática aplicada na Universidade de Kansas City (agora conhecida como Universidade de Missouri-Kansas City) e em 1955 um Ph.D. em matemática pela Caltech sob a supervisão de Robert P. Dilworth. A Universidade de Missouri-Kansas City o honrou com um Doutor Honorário em Letras Humanas em maio de 1999. Depois de ensinar matemática na Cornell University e na Ohio State University, Hartmanis ingressou no General Electric Research Laboratory em 1958. Enquanto na General Electric, ele desenvolveu muitos princípios da teoria da complexidade computacional. Em 1965, tornou-se professor na Universidade de Cornell. Ele foi um dos fundadores e o primeiro presidente do departamento de ciência da computação (que foi um dos primeiros departamentos de ciência da computação do mundo). Hartmanis contribuiu para os esforços nacionais para o avanço da ciência e engenharia da computação (CS&E) de várias maneiras. Mais significativamente, ele presidiu o estudo do Conselho Nacional de Pesquisa que resultou na publicação de 1992 Computing the Future – A Broad Agenda for Computer Science and Engineering, que fez recomendações com base em suas prioridades para sustentar o esforço central em CS&E, para ampliar o campo e para melhorar a educação de graduação em CS&E. Foi diretor assistente da National Science Foundation (NSF) Directorate of Computer and Information Science and Engineering (CISE) de 1996 a 1998. Em 1989, Hartmanis foi eleito membro da Academia Nacional de Engenharia por contribuições fundamentais à teoria da complexidade computacional e à pesquisa e educação em computação. Foi membro da Association for Computing Machinery e da American Mathematical Society, também membro da National Academy of Sciences. Ele também era um membro estrangeiro da Academia de Ciências da Letônia, que lhe concedeu sua Grande Medalha em 2001 por suas contribuições à ciência da computação. Hartmanis morreu em 29 de julho de 2022.

Complexidade computacional: contribuições fundamentais

Em 1993, Hartmanis e R.E. Stearns recebido o maior prêmio em ciência da computação, o Prêmio Turing. A citação diz, "Em reconhecimento ao seu trabalho seminal que estabeleceu as bases para o campo da teoria da complexidade computacional." O papel deles definiu a noção fundamental de uma classe de Complexidade, uma forma de classificar problemas computacionais de acordo com o tempo necessário para resolvê-los. Eles passaram a provar uma série de resultados fundamentais, como a Teorema da hierarquia temporal. Em sua própria palestra no Turing Award, Richard M. Karp observa que "é o artigo de 1965 de Juris Hartmanis e Richard Stearns que marca o início da era moderna da teoria da complexidade." Com P.M. Lewis II, Hartmanis e Stearns também definiram classes de complexidade com base no uso do espaço e provaram o primeiro teorema da hierarquia espacial. No mesmo ano eles também provou que toda linguagem livre de contexto tem complexidade espacial (log n)2, que continha a ideia essencial que levou ao teorema de Savitch sobre a complexidade do espaço. Hartmanis continuou a fazer signi