[HN Gopher] Who first thought of the notion of Polynomial Time?
___________________________________________________________________
Who first thought of the notion of Polynomial Time?
Author : furcyd
Score : 74 points
Date : 2022-11-15 11:45 UTC (1 days ago)
(HTM) web link (blog.computationalcomplexity.org)
(TXT) w3m dump (blog.computationalcomplexity.org)
| icapybara wrote:
| 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.
| schoen wrote:
| 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)^k1 vs. k2*n" is pretty darn similar to the
| way we think about this today!
| steppi wrote:
| Very interesting. I wasn't aware of Pocklington. Some other early
| work in addition to the correspondence between Godel and von
| Neumann mentioned in another comment:
|
| The French Mathematician Gabriel Lame 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] Lame, 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...
| stefantalpalaru wrote:
| aatd86 wrote:
| Doesn't it stem from series expansion?
| taylorius wrote:
| Seems to spring naturally from the idea of an algorithm using
| nested loops, I've always thought.
| danbruc wrote:
| 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 Godel 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...
___________________________________________________________________
(page generated 2022-11-16 23:01 UTC)