Hartmanis and Stearns: Measuring the Cost of Computation

The Refugee and the Game Theorist

Juris Hartmanis was born in Riga on 5 July 1928. His father Mārtiņš was a general in the Latvian Army; after the Soviet occupation of 1940 he was arrested and died in prison. The family left Latvia in 1944 as refugees, first to Germany, where Hartmanis took a physics degree at Marburg, then to the United States. He added a master’s in mathematics at Kansas City in 1951 and a doctorate in mathematics at Caltech in 1955 under Robert P. Dilworth, a lattice theorist. After teaching stints at Cornell and Ohio State he joined the General Electric Research Laboratory in Schenectady, New York, in 1958.

Richard Edwin Stearns was born on 5 July 1936, eight years to the day after Hartmanis, in Caldwell, New Jersey. He read mathematics at Carleton College, then took a Princeton doctorate in 1961 under Harold W. Kuhn with a thesis on three-person cooperative games without side payments, which is game theory and not computing at all. He had spent the summer of 1960 at the GE laboratory working with Hartmanis, and went back permanently once the degree was finished.

GE’s Information Studies Branch paid two mathematicians to think about machines without asking what product would come of it. Their first joint work was on decomposing sequential machines, breaking a finite-state machine into smaller ones that together do the same job; it filled a run of papers and a book in 1966.

The Problem With Counting Steps

The obstacle to a theory of computational cost was that cost seemed to depend on the machine. An algorithm that takes a thousand steps on one computer takes four hundred on another with a richer instruction set, and any claim about difficulty could be answered with “not on my hardware.”

In November 1962 Hartmanis and Stearns settled it by measuring on Turing machines and by asking not how many steps a computation takes but how the number of steps grows as the input gets longer. A machine that runs in time proportional to n² stays quadratic whether each step is fast or slow, and translating a program from one reasonable machine model to another changes the constant, not the growth rate. That made difficulty a property of the problem rather than of the equipment.

The Transactions of the American Mathematical Society received the paper on 2 April 1963 and a revised version on 30 August 1963. It appeared in May 1965 as “On the Computational Complexity of Algorithms”, which is where the field got its name.

The Time Hierarchy Theorem

The paper’s central result is that the classification is not a formality: it has infinitely many levels, and each one is genuinely inhabited. Given any sensible time bound, there are problems that a Turing machine can solve within a slightly larger bound and cannot solve within the smaller one. More time buys strictly more computing power, forever, with no ceiling.

That is a statement about limits, proved by diagonalisation in the manner of Turing’s undecidability argument, and it is one of the few things about complexity classes that anyone can actually prove. The contrast with what came later is unflattering: P versus NP asks whether two particular classes differ, and after fifty years nobody can prove they do, though the hierarchy theorem shows that classes separated by a big enough gap in the same resource must.

A companion paper the same year, written with Philip M. Lewis II, did the equivalent for memory and introduced a machine model with a separate read-only input tape, which is what makes it meaningful to talk about a computation using less space than its own input.

Cornell

Hartmanis left GE in 1965 to become the founding chair of Cornell’s new Department of Computer Science, one of the first anywhere. He chaired it in three separate stretches (1965 to 1971, 1977 to 1983, and 1992 to 1993), retired in 2001, and spent 1996 to 1998 as an assistant director of the National Science Foundation, where the argument he had to make was the institutional version of his research: that computing is a science with its own subject matter and not a service department for physics and engineering. He died in Ithaca on 29 July 2022, aged 94.

Stearns stayed at GE until 1978, then moved to the State University of New York at Albany, chairing the department from 1982 to 1989 and retiring in 2000. His later work reached well outside complexity: with Rosenkrantz and Lewis he developed the theory of LL(k) grammars that underlies practical top-down parsing, and his work on concurrency established serializability as the correctness condition for database transactions. He is still living.

The 1993 Turing Award citation reads “in recognition of their seminal paper which established the foundations for the field of computational complexity theory.” In his own Turing Award lecture, Richard Karp said it is the 1965 paper “that marks the beginning of the modern era of complexity theory.” The habit it created is now so ordinary that its origin is invisible: when a working programmer says an algorithm is O(n log n) and means something about the algorithm rather than about the laptop it ran on, that is the 1965 paper talking.

📚 Sources

• Hartmanis, J. & Stearns, R. E.: “On the Computational Complexity of Algorithms”, Transactions of the American Mathematical Society 117, May 1965: the founding paper, with the term “computational complexity” and the time hierarchy theorem.
• Stearns, R. E., Hartmanis, J. & Lewis, P. M. II: “Hierarchies of memory limited computations”, 6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965: the space-bounded companion paper and the separate input tape model.
• Rosenkrantz, D. J. & Stearns, R. E.: “Properties of deterministic top-down grammars”, Information and Control, October 1970: the LL(k) parsing theory.
• Juris Hartmanis: Wikipedia; birth 5 July 1928 in Riga, his father’s arrest and death, the 1944 flight, Marburg, Kansas City 1951, Caltech doctorate 1955 under Dilworth, GE from 1958, Cornell 1965, NSF 1996–1998, death 29 July 2022.
• Juris Hartmanis, first CS department chair, dies at 94: Cornell Chronicle; the three terms as chair, retirement in 2001, GE years, death at 94.
• Richard E. Stearns: Wikipedia; birth 5 July 1936 in Caldwell, Carleton, Princeton doctorate 1961 under Kuhn on three-person cooperative games, SUNY Albany.
• Richard E. Stearns: A.M. Turing Award biography: ACM; the summer of 1960 at GE, sequential machine decomposition and the 1966 book, the 1965 papers, LL(k) grammars, database serializability, Albany chairmanship 1982–1989 and retirement in 2000.
• Juris Hartmanis: A.M. Turing Award biography: ACM; the citation text, the Marburg physics degree of 1949, Kansas City M.A. 1951 in mathematics, the Cornell and Ohio State posts of 1955–1958, GE 1958–1965, and death on 29 July 2022 in Ithaca, NY.
• Fortnow, L.: “Fifty Years of Computational Complexity” (2012): November 1962 as the month the time-as-a-function-of-input-length idea was worked out, dated from Hartmanis’s logbook.
• Karp, R. M.: “Combinatorics, complexity, and randomness”, Turing Award lecture, Communications of the ACM 29(2), February 1986: the “beginning of the modern era of complexity theory” assessment.