Who first thought of the notion of Polynomial Time? | Hacker News Reader

Who first thought of the notion of Polynomial Time?

blog.computationalcomplexity.org

87 pointsfurcyd10 comments

As one of the comments under the article mentions, there is some discussion of what is now called P versus NP in the correspondence between Gödel and Von Neumann from 1956. Which is earlier than Cobham but later than Pocklington and was itself only discovered in the late 80s. [1][2]

[1] http://www.cs.cmu.edu/~odonnell/15455-s17/hartmanis-on-godel...

[2] https://www.cambridge.org/core/journals/bulletin-of-symbolic...

Very interesting. I wasn't aware of Pocklington. Some other early work in addition to the correspondence between Gödel and von Neumann mentioned in another comment:

The French Mathematician Gabriel Lamé noted in 1845 that the Euclidean algorithm for finding the greatest common divisor of two numbers is efficient because the number of steps grows linearly with the number of digits in the input. [1]

John Forbes Nash wrote a letter to the NSA discussing applications of what is now known as the P vs NP to cryptography in 1955. The letter was declassified in 2012. [2]

[1] Lamé, Gabriel. Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. 1844.

[2] https://www.nsa.gov/portals/75/documents/news-features/decla...

Physicists and engineers think about things like that all the time (e.g. "gravity dies off like 1/r^2"), so I'd guess it was just a physics idea that got applied to algorithms. Probably not an "aha!" moment.

A somewhat surprisingly modern thing about Pocklington's observation is that he treats all polynomials as equivalent for his purposes:

> the labour required here is proportional to a power of the logarithm of the modulus, not to the modulus itself or its square root as in the indirect processes, and hence see that in the case of a large modulus the direct process will be much quicker than the indirect

Specifically, he's pointing out that asymptotically any power of the logarithm of n will be smaller than a constant times n.

Physicists also naturally know about asymptotic comparisons, but the "this algorithm asymptotically beats that algorithm because it's (log n)^k₁ vs. k₂*n" is pretty darn similar to the way we think about this today!

No, he meant physicists works exactly like that to find the form of equations and what to ignore, like what a field looks like in near distance or long distance etc, it isn't a new style of thinking at all. Its a part of higher level courses and its over a century old at least since it applies to energy transportation in fields etc.

Something like dimensional analysis?

Seems to spring naturally from the idea of an algorithm using nested loops, I've always thought.

In her Ph.D. thesis in 1926, Grete Hermann worked out the time complexity of different operations in abstract algebra. This is a relatively early example of someone taking time complexity seriously.

Doesn't it stem from series expansion?

Lime green is an objectively terrible background color.

Reply on news.ycombinator.com