Juris Hartmanis (July 5, 1928 – July 29, 2022) was a Latvian-born American
computer scientist
A computer scientist is a person who is trained in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...
and
computational theorist
In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., ...
who, with
Richard E. Stearns
Richard Edwin Stearns (born July 5, 1936) is a prominent computer scientist who, with Juris Hartmanis, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational co ...
, 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 compu ...
"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 relating these classes to each other. A computational problem is a task solved by ...
".
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
Astrid Ivask (born Astrīde Helēna Hartmane; August 7, 1926 – March 24, 2015) was a Latvian-American poet.
Biography
She was born Astrīde Helēna Hartmane in Riga, the daughter of Mārtiņš Hartmanis, a Latvian Army General, and Irma Mari ...
. 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
World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...
, 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 is the second most populous country in Europe after Russia, and the most populous member state of the European Union. Germany is situated betwe ...
, where Juris Hartmanis received the equivalent of a master's degree in physics from the
University of Marburg
The Philipps University of Marburg (german: Philipps-Universität Marburg) was founded in 1527 by Philip I, Landgrave of Hesse, which makes it one of Germany's oldest universities and the oldest still operating Protestant university in the wor ...
. He then moved to the
United States
The United States of America (U.S.A. or USA), commonly known as the United States (U.S. or US) or America, is a country primarily located in North America. It consists of 50 states, a federal district, five major unincorporated territorie ...
, 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) is a public research university in Kansas City, Missouri. UMKC is part of the University of Missouri System and one of only two member universities with a medical school. As of 2020, the university ...
) and in 1955 a
Ph.D.
A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is a ...
in mathematics from
Caltech
The California Institute of Technology (branded as Caltech or CIT)The university itself only spells its short form as "Caltech"; the institution considers other spellings such a"Cal Tech" and "CalTech" incorrect. The institute is also occasional ...
under the supervision of
Robert P. Dilworth
Robert Palmer Dilworth (December 2, 1914 – October 29, 1993) was an American mathematician. His primary research area was lattice theory; his biography at the MacTutor History of Mathematics archive states "it would not be an exaggeration to say ...
.
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 statutory land-grant research university based in Ithaca, New York. It is a member of the Ivy League. Founded in 1865 by Ezra Cornell and Andrew Dickson White, Cornell was founded with the intention to teach an ...
and
Ohio State University
The Ohio State University, commonly called Ohio State or OSU, is a public land-grant research university in Columbus, Ohio. A member of the University System of Ohio, it has been ranked by major institutional rankings among the best publ ...
, Hartmanis joined the
General Electric
General Electric Company (GE) is an American multinational conglomerate founded in 1892, and incorporated in New York state and headquartered in Boston. The company operated in sectors including healthcare, aviation, power, renewable energ ...
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
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
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 National Research Council may refer to:
* National Research Council (Canada), sponsoring research and development
* National Research Council (Italy), scientific and technological research, Rome
* National Research Council (United States), part of ...
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 National Science Foundation (NSF) is an independent agency of the United States government that supports fundamental research and education in all the non-medical fields of science and engineering. Its medical counterpart is the National I ...
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, non-governmental organization. The National Academy of Engineering is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy ...
for fundamental contributions to computational complexity theory and to research and education in computing. He was a
Fellow
A fellow is a concept whose exact meaning depends on context.
In learned or professional societies, it refers to a privileged member who is specially elected in recognition of their work and achievements.
Within the context of higher education ...
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 member ...
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, 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 Nati ...
.
[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, 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 Nati ...
, April 30, 2013. He was also a foreign member of the
Latvian Academy of Sciences
The Latvian Academy of Sciences ( lv, Latvijas Zinātņu akadēmija) is the official Academy of Sciences, science academy of Latvia and is an association of the country's foremost scientists. The academy was founded as the ''Latvian SSR Academy o ...
,
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 compu ...
. 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
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
, 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 computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, ...
. In his own Turing Award lecture,
Richard M. Karp
Richard Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing ...
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 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
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 function f\in\Omega(\log(n)),
:\mathsf\left(f\lef ...
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 Von Neumann may refer to:
* John von Neumann (1903–1957), a Hungarian American mathematician
* Von Neumann family
* Von Neumann (surname), a German surname
* Von Neumann (crater), a lunar impact crater
See also
* Von Neumann algebra
* Von Ne ...
brought fresh insight
into the early history of computational complexity before his landmark paper with Stearns,
touching on interactions among
Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalysis, cryptanalyst, philosopher, and mathematical and theoretical biology, theoretical biologist. Turing was high ...
,
Gödel,
Church
Church may refer to:
Religion
* Church (building), a building for Christian religious activities
* Church (congregation), a local congregation of a Christian denomination
* Church service, a formalized period of Christian communal worship
* Chris ...
,
Post
Post or POST commonly refers to:
*Mail, the postal system, especially in Commonwealth of Nations countries
**An Post, the Irish national postal service
**Canada Post, Canadian postal service
**Deutsche Post, German postal service
**Iraqi Post, Ira ...
, 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)
The American Association for the Advancement of Science (AAAS) is an American international non-profit organization with the stated goals of promoting cooperation among scientists, defending scientific freedom, encouraging scientific respons ...
, 1981
* Member,
National Academy of Engineering
The National Academy of Engineering (NAE) is an American nonprofit, non-governmental organization. The National Academy of Engineering is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy ...
, 1989
* Member (foreign):
Latvian Academy of Sciences
The Latvian Academy of Sciences ( lv, Latvijas Zinātņu akadēmija) is the official Academy of Sciences, science academy of Latvia and is an association of the country's foremost scientists. The academy was founded as the ''Latvian SSR Academy o ...
,
1990
* Member,
American Academy of Arts and Sciences
The American Academy of Arts and Sciences (abbreviation: AAA&S) 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 ...
, 1992
*
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 compu ...
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 ( lv, Latvijas Zinātņu akadēmija) is the official Academy of Sciences, science academy of Latvia and is an association of the country's foremost scientists. The academy was founded as the ''Latvian SSR Academy o ...
, 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, 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 Nati ...
,
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
David Gries (born April 26, 1939 in Flushing, Queens, New York) is an American computer scientist at Cornell University, United States mainly known for his books ''The Science of Programming'' (1981) and ''A Logical Approach to Discrete Math'' ( ...
interviews Hartmanis for the Cornell ecommons collection,
2010
*
Len Shustek interviews Hartmanis in an article in ''
Communications of the ACM
''Communications of the ACM'' is the monthly journal of the Association for Computing Machinery (ACM). It was established in 1958, with Saul Rosen as its first managing editor. It is sent to all ACM members.
Articles are intended for readers with ...
'',
2015
*
David Gries
David Gries (born April 26, 1939 in Flushing, Queens, New York) is an American computer scientist at Cornell University, United States mainly known for his books ''The Science of Programming'' (1981) and ''A Logical Approach to Discrete Math'' ( ...
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 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