Today the basic concepts of complexity theory are firmly ensconced in the bedrock of computer science, but that wasn't always the case. As late as 1965, computer scientists knew that some problems—such as finding an optimal schedule for airlines—seemed much more difficult than other problems: searching for a person's name in a sorted phonebook, for example. Computing professionals lacked the concepts to discuss these issues rigorously. They didn't even have the vocabulary.
That changed in 1965 when Juris Hartmanis and Richard E. Stearns published their groundbreaking paper "On the Computational Complexity of Algorithms." That article introduced the concept of a complexity class, providing a straightforward way to reason about complexity using multitape Turing machines, and mathematically proved that there are an infinite number of complexity classes. The paper set the stage for the discovery of space complexity later that year by the same authors, and of the NP-complete complexity class in 1971, independently by Stephen Cook and Leonid Levin.
For this work, Hartmanis and Stearns were awarded the 1993 ACM A.M. Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory."
ACM Fellow Juris Hartmanis died on July 29, 2022, at 94. In addition to being the co-inventor of complexity theory, he was the founding chair of the Cornell Computer Science Department in 1965—one of the first in the world—where he mentored generations of students and faculty members in the emerging field. Indeed, the numerous tributes and personal testaments to Hartmanis that appeared shortly after his death make it clear that he will be remembered as much for his teaching, friendship, and leadership of the computer science community as for his award-winning brilliance.
"I'm immensely grateful to have known him," wrote MIT professor Ryan Williams in a public memorial. Williams first met Hartmanis when he was an undergraduate at Cornell in 1999. Williams had struggled in his introduction to computing theory course, then took Hartmanis' graduate complexity course, during which all theory concepts snapped into place. But what really made the difference, Williams wrote, was the mentoring. "Without his faith, I'd have never become a theoretical computer scientist. Without his initial influence, I'd have never been a good one."
Hartmanis would serve as chair of Cornell's CS department two other times (1977–1983 and 1992–1993). He retired in 2001 but remained on faculty as the Walter R. Read Professor of Computer Science and Engineering, Emeritus.
I'm immensely grateful to have known [Hartmanis]. Without his faith, I'd have never become a theoretical computer scientist. Without his initial influence, I'd have never been a good one. RYAN WILLIAMS PROFESSOR OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE MASSACHUSETTS INSTITUTE OF TECHNOLOGY
In April 1990, he became chair of a newly created National Research Council committee with the mission of assessing "the scope and direction of computer science and technology." The result was the 1992 National Academies report Computing the Future: A Broader Agenda for Computer Science and Engineering. That influential 288-page report evaluated the U.S. government's support for Computer Science and Engineering research—support that many felt was inadequate and jeopardized not only U.S. leadership but the very future of computing.
Herbert Lin, who co-edited the report with Hartmanis, had recently joined the National Academies Computer Science and Telecommunications Board as a staff officer. "Juris was the first real computer scientist with whom I ever had a close working relationship," recalls Lin. "Collaborating with him on Computing the Future, he was open to learning about the realities of U.S. science policy, and he was patient with me as he introduced me to the culture of computer science. He didn't have to treat me as a peer—but he did (and spawned a decades-long relationship). I will always be grateful that our paths crossed for so long and so fortuitously."
In another S&T leadership role, Hartmanis served as assistant director of the National Science Foundation (NSF) Directorate of Computer and Information Science and Engineering (CISE) from 1996 to 1998.
Hartmanis became a Fellow of the American Association for the Advancement of Science in 1981, of the American Academy of Arts and Sciences in 1992, an ACM Fellow in 1994, and a National Academy of Engineering member in 1989. He was also a Fellow of the American Mathematical Society and a National Academy of Sciences member. In 2000, the Computing Research Association awarded Juris their Distinguished Service Award. In 2001, the Latvian Academy of Sciences awarded him their Grand Medal for his contributions to computer science.
Figure. Juris Hartmanis photographed at Cornell University, Ithaca, NY, in 1993.
Hartmanis was born in 1928 in Latvia. He had a pleasant and uneventful childhood until the Soviet Union invaded Latvia in June 1940 as part of the secret pact between Hitler and Stalin. Juris' father, a Latvian army general, was arrested, sent to Moscow for trial, and eventually executed. Germany betrayed Russia and retook Latvia in 1941; Hartmanis, his mother, and his sister fled west into Germany in 1944 when the Soviets were poised to retake the country.
After WWII, Hartmanis studied physics at the University of Marburg. He moved to the U.S. in 1951 and eventually earned a Ph.D. in mathematics from Caltech in 1955. After graduating, he taught as an instructor at Cornell for two years and was an assistant professor at Ohio State University for the 1957–1958 academic year. In 1958, he joined the General Electric Research Laboratory in Schenectady, NY.
Richard Stearns joined G.E. in 1961. In 1963 the duo submitted the first draft of their complexity paper to Transactions of the American Mathematical Society, which the journal finally published in May 1965. That same year, Hartmanis returned to Cornell (with Hartmanis, Stearns was also elevated to the rank of ACM Fellow in 1994).
Hartmanis was well-known for being kind, patient, thoughtful, witty, and for trying to pack too much into his lectures. He enjoyed sailing on Cayuga Lake and frequently entertained faculty and out-of-town visitors at his house. His oldest daughter has speculated that this influenced her to major in hotel administration and hospitality at Cornell, spend several years in hotel management, and ultimately return to Cornell to teach hotel management; her younger sister became a sous chef.
Juris Hartmanis is survived by three children, four grandchildren, and two great-grandchildren.a
The Digital Library is published by the Association for Computing Machinery. Copyright © 2022 ACM, Inc.