History
Kozen states that Cobham and Edmonds are "generally credited with the invention of the notion of polynomial time." Cobham invented the class as a robust way of characterizing efficient algorithms, leading to Cobham's thesis. However, H. C. Pocklington, in a 1910 paper, analyzed two algorithms for solving quadratic congruences, and observed that one took time "proportional to a power of the logarithm of the modulus" and contrasted this with one that took time proportional "to the modulus itself or its square root", thus explicitly drawing a distinction between an algorithm that ran in polynomial time versus one that did not.
Read more about this topic: P (complexity)
Famous quotes containing the word history:
“I believe that in the history of art and of thought there has always been at every living moment of culture a “will to renewal.” This is not the prerogative of the last decade only. All history is nothing but a succession of “crises”Mof rupture, repudiation and resistance.... When there is no “crisis,” there is stagnation, petrification and death. All thought, all art is aggressive.”
—Eugène Ionesco (b. 1912)
“If you look at the 150 years of modern China’s history since the Opium Wars, then you can’t avoid the conclusion that the last 15 years are the best 15 years in China’s modern history.”
—J. Stapleton Roy (b. 1935)
“A country grows in history not only because of the heroism of its troops on the field of battle, it grows also when it turns to justice and to right for the conservation of its interests.”
—Aristide Briand (1862–1932)