Juris Hartmanis

Juris Hartmanis (July 5, 1928 – July 29, 2022) was a Latvian-born American computer scientist and computational theorist who, with Richard E. Stearns, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory".
Life and career
Hartmanis was born in Latvia on July 5, 1928. He was a son of , a general in the Latvian Army, and Irma Marija Hartmane. He was the younger brother of the poet Astrid Ivask. After the Soviet Union occupied Latvia in 1940, Mārtiņš Hartmanis was arrested by the Soviets and died in a prison. Later in World War II, the wife and children of Mārtiņš Hartmanis left Latvia in 1944 as refugees, fearing for their safety if the Soviet Union took over Latvia again.
They first moved to Germany, where Juris Hartmanis received the equivalent of a master's degree in physics from the University of Marburg. He then moved to the United States, where in 1951 he received a master's degree in applied mathematics at the University of Kansas City (now known as the University of Missouri–Kansas City) and in 1955 a Ph.D. in mathematics from Caltech under the supervision of Robert P. Dilworth. The University of Missouri–Kansas City honored him with an Honorary Doctor of Humane Letters in May 1999.
After teaching mathematics at Cornell University and Ohio State University, Hartmanis joined the General Electric Research Laboratory in 1958. While at General Electric, he developed many principles of computational complexity theory. In 1965, he became a professor at Cornell University. He was one of the founders and the first chair of its computer science department (which was one of the first computer science departments in the world).
Hartmanis contributed to national efforts to advance computer science and engineering (CS&E) in many ways. Most significantly, he chaired the National Research Council study that resulted in the 1992 publication Computing the Future – A Broad Agenda for Computer Science and Engineering, which made recommendations based on its priorities to sustain the core effort in CS&E, to broaden the field, and to improve undergrad education in CS&E. He was assistant director of the National Science Foundation (NSF) Directorate of Computer and Information Science and Engineering (CISE) from 1996 to 1998.
In 1989, Hartmanis was elected as a member into the National Academy of Engineering for fundamental contributions to computational complexity theory and to research and education in computing. He was a Fellow of the Association for Computing Machinery and of the American Mathematical Society, also a member of the National Academy of Sciences. He was also a foreign member of the Latvian Academy of Sciences, which bestowed him their in 2001 for his contributions to computer science.
Hartmanis died on July 29, 2022.
Computational complexity: foundational contributions
In 1993, Hartmanis and R.E. Stearns received
the highest prize in computer science, the Turing Award. The citation reads,
"In recognition of their seminal paper which established the foundations for the field
of computational complexity theory."
Their paper
defined the foundational notion of a Complexity class, a way of
classifying computational problems according to the time required to solve them.
They went on to prove a number of fundamental results such as the
Time hierarchy theorem. In his own Turing Award lecture, Richard M. Karp remarks that "[I]t is the 1965 paper by Juris Hartmanis and Richard Stearns that marks the beginning of the modern era of
complexity theory."
With P.M. Lewis II, Hartmanis and Stearns also defined complexity classes based on space usage and proved
the first space hierarchy theorem. In the same year they
also proved that every context-free language has deterministic
space complexity , which contained the essential idea that led
to Savitch's theorem on space complexity.
Hartmanis continued to make significant contributions to the field of computational complexity for decades. With Leonard Berman, he proved that all natural NP-complete languages are polynomial-time isomorphic and conjectured
that this holds for all NP-complete sets. Although
the conjecture itself remains open, it has led to
a large body of research on the structure of NP-complete sets, culminating
in Mahaney's theorem on the nonexistence of sparse NP-complete sets. He and his coauthors also
defined the Boolean hierarchy.
Hartmanis's 1981 article gives a personal account of developments in this area and in automata theory and discusses
the underlying beliefs and philosophy that guided his research. The book
written in honor of his 60th birthday, in particular, the chapter by Stearns, is a valuable resource on computational complexity.
In the late 1980's, Hartmanis's exposition on a newly discovered letter dated 20 March 1956
from Gödel to von Neumann brought fresh insight
into the early history of computational complexity before his landmark paper with Stearns,
touching on interactions among Turing, Gödel,
Church, Post, and Kleene.
Gödel, in this letter, was the first to question whether a problem equivalent to an NP-complete
problem could be solved in quadratic or linear time, presaging the P = NP? question.
Awards
Fellow, American Association for the Advancement of Science (AAAS), 1981
Member, National Academy of Engineering, 1989
Member (foreign): Latvian Academy of Sciences, 1990
Member, American Academy of Arts and Sciences, 1992
ACM Turing Award 1993
Humboldt Foundation Research Award, 1993
Charter Fellow, ACM, 1994
Honorary Doctor of Humane Letters, 1999
Computing Research Association (CRA) Distinguished Service Award, 2000
of the Latvian Academy of Sciences, 2001
ACM Distinguished Service Award, 2013
Inaugural Fellow, American Mathematical Society, 2013
Member, National Academy of Sciences, 2013
Selected publications
Books
Algebraic Structure Theory of Sequential Machines 1966 (with R.E. Stearns)
Feasible Computations and Provable Complexity Properties 1978
Computational Complexity Theory (ed.) 1989
Computing the Future: A broader agenda for computer science and engineering (ed.) 1992 (with Herbert Lin)
Selected articles
"Computational complexity of recursive sequences" 1964 (with R.E. Stearns)
"Classifications of computations by time and memory requirements" 1965 (with P.M. Lewis and R.E. Stearns)
"Hierarchies of memory limited computations" 1965 (with P.M. Lewis and R.E. Stearns)
"On the computational complexity of algorithms" 1965 (with R.E. Stearns)
Memory bounds for recognition of context-free and context-sensitive languages 1965 (with P.M. Lewis and R.E. Stearns)
"On isomorphisms and density of NP and other complete sets" 1977 (with L. Berman)
"Observations about the development of theoretical computer science" 1981
"Gödel, von Neumann, and the P =? NP problem" 1989
Interviews
Juris Hartmanis has been interviewed four times. Videos are available for two of them. The most far-reaching one is by William Aspray.
William Aspray interviews Hartmanis for the ACM Oral History interviews, 2009
David Gries interviews Hartmanis for the Cornell ecommons collection, 2010
Len Shustek interviews Hartmanis in an article in Communications of the ACM, 2015
David Gries interviews Hartmanis as ACM Turing Award recipient, 2018
References
External links
Hartmanis biography at A.M. TURING AWARD, Short Annotated Bibliography
Hartmanis biography at Cornell
1928 births
2022 deaths
20th-century American engineers
20th-century American scientists
American computer scientists
Theoretical computer scientists
Fellows of the Association for Computing Machinery
Fellows of the American Mathematical Society
Members of the United States National Academy of Engineering
Members of the United States National Academy of Sciences
Turing Award laureates
Cornell University faculty
California Institute of Technology alumni
Latvian emigrants to the United States
Latvian World War II refugees
Santa Fe Institute people
University of Marburg alumni
University of Kansas alumni
University of Missouri–Kansas City alumni
Ohio State University faculty
Scientists from Riga