Juris Hartmanis was born on July 5, 1928, and passed away on July 29, 2022. He was a Latvian-born American computer scientist who studied how computers solve problems. Along with Richard E. Stearns, Hartmanis was awarded the 1993 ACM Turing Award. This honor recognized their important paper, which created the foundation for the field of computational complexity theory.

Life and career

Juris Hartmanis was born in Latvia on July 5, 1928. His father was Mārtiņš Hartmanis, a general in the Latvian Army, and his mother was Irma Marija Hartmane. He was the younger brother of Astrid Ivask, a poet. In 1940, the Soviet Union occupied Latvia, and Mārtiņš Hartmanis was arrested by the Soviets and died in prison. Later during World War II, Mārtiņš Hartmanis’s wife and children left Latvia in 1944 as refugees, fearing the Soviet Union might take over again.

They first moved to Germany, where Juris Hartmanis earned a master’s degree in physics from the University of Marburg. He then moved to the United States, where he received a master’s degree in applied mathematics from the University of Kansas City (now the University of Missouri–Kansas City) in 1951 and a Ph.D. in mathematics from Caltech in 1955. His doctoral advisor was Robert P. Dilworth. In 1999, the University of Missouri–Kansas City honored him with an honorary doctorate in humane letters.

After teaching mathematics at Cornell University and Ohio State University, Hartmanis joined the General Electric Research Laboratory in 1958. At General Electric, he helped develop key ideas in computational complexity theory. In 1965, he became a professor at Cornell University. He was one of the founders and the first chair of Cornell’s computer science department, which was among the first of its kind in the world.

Hartmanis supported efforts to grow computer science and engineering in many ways. He led a National Research Council study that resulted in the 1992 report Computing the Future – A Broad Agenda for Computer Science and Engineering. This report suggested ways to strengthen the field, expand its reach, and improve undergraduate education. From 1996 to 1998, he served as assistant director of the National Science Foundation’s Directorate of Computer and Information Science and Engineering.

In 1989, Hartmanis was elected to the National Academy of Engineering for his work in computational complexity theory and in computing research and education. He was a Fellow of the Association for Computing Machinery and the American Mathematical Society. He was also a member of the National Academy of Sciences and a foreign member of the Latvian Academy of Sciences, which awarded him their Grand Medal 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 award in computer science, the Turing Award. The citation said, "For their important paper that started the field of computational complexity theory." Their paper introduced the basic idea of a complexity class, a way to group computational problems based on how much time is needed to solve them. They also proved key results, such as the Time hierarchy theorem. In his own Turing Award lecture, Richard M. Karp noted 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 created complexity classes based on how much space is needed to solve problems. They proved the first space hierarchy theorem. In the same year, they showed that every context-free language can be solved using a specific amount of space, which included an idea that later helped develop Savitch's theorem on space complexity.

Hartmanis continued to make important contributions to computational complexity for many years. With Leonard Berman, he proved that all natural NP-complete languages are similar in a special way and guessed that this might be true for all NP-complete sets. Although this guess remains unproven, it led to much research on the structure of NP-complete sets, including Mahaney's theorem, which says sparse NP-complete sets do not exist. He and his coauthors also defined the Boolean hierarchy.

Hartmanis's 1981 article describes how the field of computational complexity and automata theory developed. It also explains the beliefs and ideas that guided his research. A book written to celebrate his 60th birthday, especially the chapter by Stearns, is a helpful resource about computational complexity.

In the late 1980s, Hartmanis shared a newly discovered letter from Gödel to von Neumann, dated March 20, 1956. This letter provided new insights into the early history of computational complexity before Hartmanis and Stearns's landmark paper. It also described how Turing, Gödel, Church, Post, and Kleene interacted. In the letter, Gödel asked whether a problem similar to an NP-complete problem could be solved quickly, which introduced the question of whether P equals NP.

Awards

Fellow of the American Association for the Advancement of Science (AAAS), 1981
Member of the National Academy of Engineering, 1989
Member of the Latvian Academy of Sciences (foreign member), 1990
Member of the American Academy of Arts and Sciences, 1992
Received the ACM Turing Award, 1993
Received the Humboldt Foundation Research Award, 1993
Charter Fellow of the ACM, 1994
Honorary Doctor of Humane Letters, 1999
Received the Computing Research Association (CRA) Distinguished Service Award, 2000
Received the Grand Medal [lv] of the Latvian Academy of Sciences, 2001
Received the ACM Distinguished Service Award, 2013
Inaugural Fellow of the American Mathematical Society, 2013
Member of the National Academy of Sciences, 2013

Interviews

Juris Hartmanis has been interviewed four times. Videos are available for two of these interviews. The most detailed one was conducted by William Aspray.

• William Aspray conducted an interview with Hartmanis as part of the ACM Oral History project in 2009
• David Gries conducted an interview with Hartmanis for the Cornell ecommons collection in 2010
• Len Shustek conducted an interview with Hartmanis, which was published in Communications of the ACM in 2015
• David Gries conducted an interview with Hartmanis as part of the ACM Turing Award recognition in 2018