3 ms·
These letters contain some of the first discussions of computational complexity theory, and von Neumann immediately identifies P vs NP as a central problem in t
by earthicus 8y ago
These letters contain some of the first discussions of computational complexity theory, and von Neumann immediately identifies P vs NP as a central problem in the field. The work was unpublished and undeveloped, as von Neumann became ill and died around this time.
Edit: I double-checked my biography of von Neumann and in fact, as the poster below indicated, his responses (if he was able to make any) aren't available. This letter of Goedel has identified an NP problem, and he's asking if it can be solved in polynomial time, so we can't credit von Neumann for identifiying the problem with certainty.
- lqet 8y agoA common phrase you often hear when people try to explain the impressive technological leaps made in the 20th century is "war is the father of all things", meaning of course that WWII was a major catalyst for technological advancement. I always wondered if it shouldn't be phrased as "John von Neumann is the father of all things."
- SquishyPanda23 8y agoI'dd add Poincaré. John von Neumann and Henri Poincaré certainly deserve credit for a shocking amount of modern advancement in math and science.
- shmageggy 8y ago> von Neumann immediately identifies P vs NP as a central problem in the field. Do you have a source for this? I'd love to read von Neumann's reply. All I found from a search is this stackexchange answer stating that there is no known reply. https://cstheory.stackexchange.com/questions/41209/did-von-neumann-answer-to-g%C3%B6dels-letter https://cstheory.stackexchange.com/questions/41209/did-von-n...
- earthicus 8y agoMy source for learning about the exchange was a biography of von Neumann by Macrae, but i double-checked it and it appears you are correct. I was mis-remembering how much of the correspondence von Neumann was able to contribute at that point. I've corrected my original comment accordingly, thank you.