 |
| 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. |
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.
Great picture. Love the haircuts.
ReplyDeleteWere 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.
ReplyDeletePeople 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).
ReplyDeleteOther 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.
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' !
ReplyDelete