4 ms·

Who first thought of the notion of Polynomial Time?

87 points by furcyd 4y ago

stefantalpalaru 4y ago
danbruc 4y ago
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-von-neumann.pdf http://www.cs.cmu.edu/~odonnell/15455-s17/hartmanis-on-godel... [2] https://www.cambridge.org/core/journals/bulletin-of-symbolic-logic/article/abs/von-neumann-godel-and-complexity-theory/8F133F1B5742612B7E118BDE7A59AF65 https://www.cambridge.org/core/journals/bulletin-of-symbolic...
icapybara 4y ago
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 4y ago
  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!
  - Jensson 4y ago
    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.
    - schoen 4y ago
      Something like dimensional analysis?
steppi 4y ago
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/declassified-documents/nash-letters/nash_letters1.pdf https://www.nsa.gov/portals/75/documents/news-features/decla...
taylorius 4y ago
Seems to spring naturally from the idea of an algorithm using nested loops, I've always thought.
aatd86 4y ago
Doesn't it stem from series expansion?
PointyFluff 4y ago
Lime green is an objectively terrible background color.
QuesnayJr 4y ago
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.

87 points by furcyd 4y ago

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-von-neumann.pdf http://www.cs.cmu.edu/~odonnell/15455-s17/hartmanis-on-godel... [2] https://www.cambridge.org/core/journals/bulletin-of-symbolic-logic/article/abs/von-neumann-godel-and-complexity-theory/8F133F1B5742612B7E118BDE7A59AF65 https://www.cambridge.org/core/journals/bulletin-of-symbolic...

icapybara 4y ago

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 4y ago
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!
- Jensson 4y ago
  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.
  - schoen 4y ago
    Something like dimensional analysis?

steppi 4y ago

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/declassified-documents/nash-letters/nash_letters1.pdf https://www.nsa.gov/portals/75/documents/news-features/decla...

taylorius 4y ago

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

aatd86 4y ago

Doesn't it stem from series expansion?

PointyFluff 4y ago

Lime green is an objectively terrible background color.

QuesnayJr 4y ago

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.