Juris Hartmanis (July 5, 1928 – July 29, 2022) was a Latvian-born American
computer scientist
A computer scientist is a scientist who specializes in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...
and
computational theorist
A computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Common examples of computation are mathematical equation solving and the execution of computer algorithms.
Mechanical or electronic devices (or, historic ...
who, with
Richard E. Stearns, received the 1993 ACM
Turing Award
The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in the fi ...
"in recognition of their seminal paper which established the foundations for the field of
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
".
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 prison. Later in
World War II
World War II or the Second World War (1 September 1939 – 2 September 1945) was a World war, global conflict between two coalitions: the Allies of World War II, Allies and the Axis powers. World War II by country, Nearly all of the wo ...
, 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
Germany, officially the Federal Republic of Germany, is a country in Central Europe. It lies between the Baltic Sea and the North Sea to the north and the Alps to the south. Its sixteen States of Germany, constituent states have a total popu ...
, where Juris Hartmanis received the equivalent of a master's degree in physics from the
University of Marburg
The Philipps University of Marburg () is a public research university located in Marburg, Germany. It was founded in 1527 by Philip I, Landgrave of Hesse, which makes it one of Germany's oldest universities and the oldest still operating Prote ...
. He then moved to the
United States
The United States of America (USA), also known as the United States (U.S.) or America, is a country primarily located in North America. It is a federal republic of 50 U.S. state, states and a federal capital district, Washington, D.C. The 48 ...
, 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
The University of Missouri–Kansas City (UMKC or Kansas City) is a Public university, public research university in Kansas City, Missouri, United States. UMKC is part of the University of Missouri System and has a UMKC School of Medicine, medic ...
) and in 1955 a
Ph.D. in mathematics from
Caltech
The California Institute of Technology (branded as Caltech) is a private university, private research university in Pasadena, California, United States. The university is responsible for many modern scientific advancements and is among a small g ...
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
Cornell University is a Private university, private Ivy League research university based in Ithaca, New York, United States. The university was co-founded by American philanthropist Ezra Cornell and historian and educator Andrew Dickson W ...
and
Ohio State University
The Ohio State University (Ohio State or OSU) is a public university, public Land-grant university, land-grant research university in Columbus, Ohio, United States. A member of the University System of Ohio, it was founded in 1870. It is one ...
, Hartmanis joined the
General Electric Research Laboratory
General Electric Research Laboratory was the first industrial research facility in the United States. Established in 1900, the lab was home to the early technological breakthroughs of General Electric and created a research and development environ ...
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
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied 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)
The U.S. National Science Foundation (NSF) is an independent agency of the United States federal government that supports fundamental research and education in all the non-medical fields of science and engineering. Its medical counterpart is ...
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
The National Academy of Engineering (NAE) is an American Nonprofit organization, nonprofit, NGO, non-governmental organization. It is part of the National Academies of Sciences, Engineering, and Medicine (NASEM), along with the National Academ ...
for fundamental contributions to computational complexity theory and to research and education in computing. He was a
Fellow
A fellow is a title and form of address for distinguished, learned, or skilled individuals in academia, medicine, research, and industry. The exact meaning of the term differs in each field. In learned society, learned or professional society, p ...
of the
Association for Computing Machinery
The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional membe ...
and of the
American Mathematical Society
The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...
,
[List of Fellows of the American Mathematical Society](_blank)
retrieved January 19, 2013. also a member of the
National Academy of Sciences
The National Academy of Sciences (NAS) is a United States nonprofit, NGO, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the ...
.
[National Academy of Sciences Members and Foreign Associates Elected](_blank)
, National Academy of Sciences
The National Academy of Sciences (NAS) is a United States nonprofit, NGO, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the ...
, April 30, 2013. He was also a foreign member of the
Latvian Academy of Sciences
The Latvian Academy of Sciences (, ) is the official science academy of Latvia and is an association of the country's foremost scientists. The academy was founded as the ''Latvian SSR Academy of Sciences'' (). It is located in Riga. The curren ...
,
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 ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in the fi ...
. The citation reads,
"In recognition of their seminal paper which established the foundations for the field
of
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
."
Their paper
defined the foundational notion of a
Complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...
, 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 "
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. They proveded
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
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity. It states that for any space-constructable function f\in\Omega(\log(n)) ...
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 1980s, 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
Church may refer to:
Religion
* Church (building), a place/building for Christian religious activities and praying
* Church (congregation), a local congregation of a Christian denomination
* Church service, a formalized period of Christian comm ...
,
Post, and
Kleene
Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of ...
.
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
The National Academy of Engineering (NAE) is an American Nonprofit organization, nonprofit, NGO, non-governmental organization. It is part of the National Academies of Sciences, Engineering, and Medicine (NASEM), along with the National Academ ...
, 1989
* Member (foreign):
Latvian Academy of Sciences
The Latvian Academy of Sciences (, ) is the official science academy of Latvia and is an association of the country's foremost scientists. The academy was founded as the ''Latvian SSR Academy of Sciences'' (). It is located in Riga. The curren ...
,
1990
* Member,
American Academy of Arts and Sciences
The American Academy of Arts and Sciences (The Academy) is one of the oldest learned societies in the United States. It was founded in 1780 during the American Revolution by John Adams, John Hancock, James Bowdoin, Andrew Oliver, and other ...
, 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
The Latvian Academy of Sciences (, ) is the official science academy of Latvia and is an association of the country's foremost scientists. The academy was founded as the ''Latvian SSR Academy of Sciences'' (). It is located in Riga. The curren ...
, 2001
*
ACM Distinguished Service Award,
2013
* Inaugural Fellow,
American Mathematical Society
The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...
,
2013
* Member,
National Academy of Sciences
The National Academy of Sciences (NAS) is a United States nonprofit, NGO, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the ...
,
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
''Communications of the ACM'' (''CACM'') is the monthly journal of the Association for Computing Machinery (ACM).
History
It was established in 1958, with Saul Rosen as its first managing editor. It is sent to all ACM members.
Articles are i ...
'',
2015
*
David Gries interviews Hartmanis as ACM Turing Award recipient,
2018
References
External links
Hartmanis biography at A.M. TURING AWARDShort Annotated Bibliography*
{{DEFAULTSORT:Hartmanis, Juris
1928 births
2022 deaths
20th-century American engineers
20th-century American scientists
American theoretical computer scientists
1994 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