History
Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous foundations were laid out by various researchers. Most influential among these was the definition of Turing machines by Alan Turing in 1936, which turned out to be a very robust and flexible notion of computer.
Fortnow & Homer (2003) date the beginning of systematic studies in computational complexity to the seminal paper "On the Computational Complexity of Algorithms" by Juris Hartmanis and Richard Stearns (1965), which laid out the definitions of time and space complexity and proved the hierarchy theorems. Also, in 1965 Edmonds defined a "good" algorithm as one with running time bounded by a polynomial of the input size.
According to Fortnow & Homer (2003), earlier papers studying problems solvable by Turing machines with specific bounded resources include John Myhill's definition of linear bounded automata (Myhill 1960), Raymond Smullyan's study of rudimentary sets (1961), as well as Hisao Yamada's paper on real-time computations (1962). Somewhat earlier, Boris Trakhtenbrot (1956), a pioneer in the field from the USSR, studied another specific complexity measure. As he remembers:
However, initial interest was increasingly set aside in favor of computational complexity, an exciting fusion of combinatorial methods, inherited from switching theory, with the conceptual arsenal of the theory of algorithms. These ideas had occurred to me earlier in 1955 when I coined the term "signalizing function", which is nowadays commonly known as "complexity measure". —Boris Trakhtenbrot, From Logic to Theoretical Computer Science – An Update. In: Pillars of Computer Science, LNCS 4800, Springer 2008.In 1967, Manuel Blum developed an axiomatic complexity theory based on his axioms and proved an important result, the so-called, speed-up theorem. The field really began to flourish in 1971 when the US researcher Stephen Cook and, working independently, Leonid Levin in the USSR, proved that there exist practically relevant problems that are NP-complete. In 1972, Richard Karp took this idea a leap forward with his landmark paper, "Reducibility Among Combinatorial Problems", in which he showed that 21 diverse combinatorial and graph theoretical problems, each infamous for its computational intractability, are NP-complete.
Read more about this topic: Computational Complexity Theory
Famous quotes containing the word history:
“Look through the whole history of countries professing the Romish religion, and you will uniformly find the leaven of this besetting and accursed principle of action—that the end will sanction any means.”
—Samuel Taylor Coleridge (1772–1834)
“The history of all Magazines shows plainly that those which have attained celebrity were indebted for it to articles similar in natureto Berenice—although, I grant you, far superior in style and execution. I say similar in nature. You ask me in what does this nature consist? In the ludicrous heightened into the grotesque: the fearful coloured into the horrible: the witty exaggerated into the burlesque: the singular wrought out into the strange and mystical.”
—Edgar Allan Poe (1809–1849)
“The myth of independence from the mother is abandoned in mid- life as women learn new routes around the mother—both the mother without and the mother within. A mid-life daughter may reengage with a mother or put new controls on care and set limits to love. But whatever she does, her child’s history is never finished.”
—Terri Apter (20th century)