Juris Hartmanis

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Juris Hartmanis
Juris Hartmanis(2002).jpg
Born(1928-07-05)July 5, 1928
Riga, Latvia
DiedJuly 29, 2022(2022-07-29) (aged 94)
Alma mater
AwardsTuring Award (1993)
Scientific career
FieldsComputer science
Doctoral advisorRobert P. Dilworth
Doctoral studentsAllan Borodin (1969), Dexter Kozen (1977), Neil Immerman (1980), Jin-Yi Cai (1986)[1]

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[edit]

Hartmanis was born in Latvia on July 5, 1928.[2] He was a son of Mārtiņš Hartmanis [lv],[3] a general in the Latvian Army, and 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.[6][7]

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.[8] The University of Missouri–Kansas City honored him with an Honorary Doctor of Humane Letters in May 1999.[9] 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.[15] 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).[16]

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,[17] 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)[18] 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,[19] also a member of the National Academy of Sciences.[20] He was also a foreign member of the Latvian Academy of Sciences,[21] which bestowed him their Grand Medal [lv] in 2001 for his contributions to computer science.[22]

Along with R.E. Stearns, Hartmanis received the 1993 Turing Award for a paper in which they introduced time complexity classes TIME(f(n)) and proved the time hierarchy theorem.[13] Another paper by Hartmanis from 1977, with Leonard Berman, introduced the still-unsolved Berman–Hartmanis conjecture that all NP-complete languages are polynomial-time isomorphic.[23]

Hartmanis died on July 29, 2022.[24][25]


Selected publications[edit]

  • Algebraic Structure Theory of Sequential Machines[37] 1966 (with R.E. Stearns)
  • Feasible Computations and Provable Complexity Properties[38] 1978
  • Computational Complexity Theory (ed.)[39] 1989
  • Computing the Future: A broader agenda for computer science and engineering (ed.)[40] 1992 (with Herbert Lin)
Selected articles
  • "Computational complexity of recursive sequences"[10] 1964 (with R.E. Stearns)
  • "Classifications of computations by time and memory requirements"[11] 1965 (with P.M. Lewis and R.E. Stearns)
  • "Hierarchies of memory limited computations"[12] 1965 (with P.M. Lewis and R.E. Stearns)
  • "On the computational complexity of algorithms"[13] 1965 (with R.E. Stearns)
  • Memory bounds for recognition of context-free and context-sensitive languages[41] 1965 (with P.M. Lewis and R.E. Stearns)
  • "On isomorphisms and density of NP and other complete sets"[23] 1977 (with L. Berman)
  • "Observations about the development of theoretical computer science"[14] 1981
  • "Gödel, von Neumann, and the P =? NP problem"[42] 1989


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,[4] 2009
  • David Gries interviews Hartmanis for the Cornell ecommons collection,[43] 2010
  • Len Shustek interviews Hartmanis in an article in Communications of the ACM,[44] 2015
  • David Gries interviews Hartmanis as ACM Turing Award recipient,[5] 2018


  1. ^ "Juris Hartmanis". mathgenealogy.org. Mathematics Genealogy Project. Retrieved August 4, 2022.
  2. ^ Selman, Alan L., ed. (1990). Complexity Theory Retrospective : In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988. New York, NY: Springer New York. doi:10.1007/978-1-4612-4478-3. ISBN 978-1-4612-4478-3. S2CID 31789744. Retrieved August 4, 2022.
  3. ^ In the Baltic languages, own-names are not lexical constants, but have different grammatical forms. Hartmanis must be understood as Hartman-is, whereby Hartman is the stem of the own-name, whereas the suffix -is indicates a masculine grammatical form in the Latvian language. In a similar manner, for example, the philosopher Kant is known as Kantas in the Lithuanian language.
  4. ^ a b Hartmanis, Juris (July 26, 2009). "Dr. Juris Hartmanis Interview" (text). Interviewed by William Aspray. Ithaca, New York: ACM Oral History interviews. doi:10.1145/1141880.1775727.
  5. ^ a b Hartmanis, Juris (May 17, 2018). "Juris Hartmanis, 1993 ACM Turing Award Recipient" (video). Interviewed by David Gries. Ithaca, New York: ACM.
  6. ^ In two of the interviews[4][5] cited in section #Interviews, Hartmanis talks in detail of this period of his life, in which his father was given an estate, Lestene; the Russians occupied Latvia, took his father away, and confiscated Lestene; the Germans took over once more and restored part of Lestene to his family; and the family left Latvia for Germany before the Russians invaded Latvia again.
  7. ^ "A Tribute to Astrid Ivask: A Literary Light". World Literature Today. April 2, 2015. Retrieved August 4, 2022.
  8. ^ Hartmanis, Juris (1955). Some embedding theorems for lattices (PhD thesis). Cal Tech. doi:10.7907/40KS-0T27.
  9. ^ a b "University of Missouri Honorary Degrees". University of Missouri.
  10. ^ a b —; Stearns, R.E. (November 11, 1964). Computational complexity of recursive sequences. 5th Ann. Symp. on Switching Circuit Theory and Logical Design. Princeton, New Jersey: IEEE. pp. 82–90. doi:10.1109/SWCT.1964.6.
  11. ^ a b —; Lewis, P.M.; Stearns, R.E. (May 24, 1963). Wayne A. Kalenich (ed.). Classifications of computations by time and memory requirements. Proc. IFIP Congress 65. New York City: Spartan Books, Inc., Washington, D.C. pp. 31–35. doi:10.2307/2272795. JSTOR 2272795.
  12. ^ a b —; Lewis, P.M.; Stearns, R.E. (October 6, 1965). Hierarchies of memory limited computations. FOCS 65: Proc. Sixth Ann. Symp Switching Circuit Theory and Logical Design. New York: IEEE. pp. 179–190. doi:10.1109/FOCS.1965.11.
  13. ^ a b c —; Stearns, R. E. (1965), "On the computational complexity of algorithms", Transactions of the AMS, 117: 285–306, doi:10.2307/1994208, JSTOR 1994208, MR 0170805
  14. ^ a b — (1981), "Observations about the development of theoretical computer science", IEEE Annals of the History of Computing, 3 (1): 42–51, doi:10.1109/MAHC.1981.10005, hdl:1813/6244, ISSN 1058-6180
  15. ^ These early papers developed many principles of computational complexity theory.[10][11][12][13] Hartmanis's 1981 survey paper provides extensive information on the work in computational complexity theory.[14]
  16. ^ Purdue University created the first CS Department in 1962 "History of the Department". Cornell started its CS Department in 1965, "CS Dept. timeline". as did Stanford, "CS Dept. timeline"., Carnegie Mellon, "CS Dept. history". and a few others.
  17. ^ Hartmanis, Juris; Lin, Herbert, eds. (1992). Computing the Future: A broader agenda for computer science and engineering. Washington, DC: National Academies Press. p. 288. doi:10.17226/1982. ISBN 978-0-309-04740-1.
  18. ^ "Juris Hartmanis to Lead NSF's Directorate for CISE". NSF. September 5, 1996. Retrieved August 2, 2022.
  19. ^ a b List of Fellows of the American Mathematical Society, retrieved January 19, 2013.
  20. ^ National Academy of Sciences Members and Foreign Associates Elected Archived May 27, 2013, at the Wayback Machine, National Academy of Sciences, April 30, 2013.
  21. ^ a b "Foreign members". Latvian Academy of Sciences. 1990. Retrieved July 30, 2022.
  22. ^ a b "Lielā medaļa" [Grand Medal]. www.lza.lv (in Latvian). Latvian Academy of Sciences. Archived from the original on January 6, 2022. Retrieved August 4, 2022. 2001 ... Juris Hartmanis, par izcilu ieguldījumu datorzinātņu attīstībā. [2001 ... Juris Hartmanis, for his outstanding contribution to the development of computer science.]
  23. ^ a b Berman, L.; — (1977), "On isomorphisms and density of NP and other complete sets" (PDF), SIAM Journal on Computing, 6 (2): 305–322, doi:10.1137/0206023, hdl:1813/7101, MR 0455536
  24. ^ 新智元 [Xin Zhi Yuan] (July 31, 2022). "图灵奖得主,"计算复杂性"理论奠基人Juris Hartmanis逝世,享年94岁" [Turing Award winner and founder of "computational complexity" theory, Juris Hartmanis, dies at 94]. 新浪 finance.sina.com.cn (in Simplified Chinese). Retrieved August 4, 2022.
  25. ^ Waldron, Patricia (August 4, 2022). "Juris Hartmanis, first CS department chair, dies at 94". Cornell Chronicle. Retrieved August 5, 2022.
  26. ^ "Fellows". American Association for the Advancement of Science. 1981. Retrieved July 30, 2022.
  27. ^ "NAE Website – Dr. Juris Hartmanis". National Academy of Engineering.
  28. ^ "Members". American Academy of Arts and Sciences. 1992. Retrieved July 30, 2022.
  29. ^ "Turing Award". ACM. 1993. Retrieved July 30, 2022.
  30. ^ "Alexander von Humboldt Foundation, Juris Hartmanis". Alexander von Humboldt Foundation. 1993.
  31. ^ "ACM Fellows". ACM. 1994. Retrieved July 30, 2022.
  32. ^ "Juris Hartmanis: ACM Fellow". 1994. Retrieved July 9, 2022.
  33. ^ "Distinguished Service Award". Computing Research Association. CRA. January 16, 2015. Retrieved July 30, 2022.
  34. ^ "ACM Distinguished Service Award". ACM. 2013. Retrieved July 30, 2022.
  35. ^ "Juris Hartmanis: Distinguished Service Award". 2013. Retrieved July 30, 2022.
  36. ^ "Member Emeritus". National Academy of Sciences (NAS). Retrieved July 31, 2022.
  37. ^ —; Richard E., Stearns (1966). Algebraic Structure Theory of Sequential Machines. Englewood Cliffs, N.J.: Prentice-Hall. p. 211. ISBN 0130222771.
  38. ^ — (1978). Feasible Computations and Provable Complexity Properties. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). p. 62. ISBN 978-0-898710-27-4.
  39. ^ —, ed. (1989). Computational Complexity Theory. AMS. p. 128. ISBN 978-0-8218-0131-4.
  40. ^ —; Lin, Herbert, eds. (1992). Computing the Future: A broader agenda for computer science and engineering. Washington, DC: The National Academies Press. p. 288. doi:10.17226/1982. ISBN 978-0-309-04740-1.
  41. ^ Lewis, P.M.; Stearns, R.E.; — (October 6, 1965). Memory bounds for recognition of context-free and context-sensitive languages. FOCS 65: Proc. Sixth Ann. Symp Switching Circuit Theory and Logical Design. Ann Arbor, Michigan: IEEE. pp. 191–202. doi:10.1109/FOCS.1965.14.
  42. ^ Hartmanis, Juris (1989). "Gödel, von Neumann, and the P =? NP problem". Bulletin of the European Association for Theoretical Computer Science. 38: 101–107.
  43. ^ Hartmanis, Juris (March 31, 2010). "A Conversation with Juris Hartmanis" (video). Interviewed by David Gries. Ithaca, New York: Internet-First University Press.
  44. ^ Shustek, Len (2015). "An interview with Juris Hartmanis". CACM. 58 (4): 33–37. doi:10.1145/2736346. S2CID 35051248.

External links[edit]