Thursday, May 14, 2015

Fiftieth Anniversary of the Publication of the seminal paper on Computational Complexity

Juris Hartmanis and Richard Stearns in a photo dated May 1963. The main theorem from their paper is on the board later improved by Hennie and Stearns. Photo courtesy of Richard Stearns.
The seminal paper of Juris Hartmanis and Richard Stearns, On the Computational Complexity of Algorithms, appeared in the Transactions of the American Mathematical Society in the May 1965 issue. This paper gave the name to the field of Computational Complexity which I took for the name of this blog. Hartmanis and Stearns received the Turing Award in 1993 for this work.

I've mentioned this paper several times in the blog before, including as a favorite theorem. Hartmanis and Stearns first formalized and truly popularized the idea of measuring time and other resources as a function the problem size, laying the foundation for virtually every paper in computational complexity and algorithms to follow.

Both Hartmanis and Stearns wrote about those early days. The main breakthroughs for their paper started in November 1962 and on December 31 Hartmanis wrote in his logbook "This was a good year," A good year indeed.


  1. Were earlier complexity classes like e.g. Primitive Recursive functions ever considered as being motivated by "reasonable runtimes"? Obviously they weren't that, but was that an aim? It's just kind of hard to imagine computability theory operating for like 30 years without any kind of complexity theory existing.

  2. People did study interesting subclasses of computable functions. The approach was definitional, rather than "use of resources". I believe that the Hartmanis and Stearns approach was the first that counted steps (and memory).
    Other important precursors include Rabin (who tried to define "f is harder than compute than g", and discussed, essentially, one-way functions for cryptography;
    Cobham, who wanted to formalize the notion "it is harder to multiply than to add",
    and Edmonds, who needed to define the class P to justify why his polynomial time algorithm for non-bipartite matching was a good thing, even though it was too slow for the computers that there were around. [Of course, this is an oversimplified account!]
    In any case, Hartmanis and Stearns was explicit, well argued, well written, and for all practical purposes, THE paper that launched Complexity.

  3. I talked to Hartmanis about this in 2012 and asked if they had considered using recursive function theory. He said they had and it had made things horribly complicated. Then they came across Turing machines and the whole thing became 'so simple' !