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 am not a literary man.... I am a man of science, and I am interested in that branch of Anthropology which deals with the history of human speech.”
—J.A.H. (James Augustus Henry)
“There is nothing truer than myth: history, in its attempt to “realize” myth, distorts it, stops halfway; when history claims to have “succeeded” this is nothing but humbug and mystification. Everything we dream is “realizable.” Reality does not have to be: it is simply what it is.”
—Eugène Ionesco (b. 1912)
“Perhaps universal history is the history of the diverse intonation of some metaphors.”
—Jorge Luis Borges (1899–1986)