Hacker News Reader

Comment by segfaultbuserr | Hacker News Reader

Could someone adds the historical background of Godel's question?

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.

A 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."

I'dd add Poincaré.

John von Neumann and Henri Poincaré certainly deserve credit for a shocking amount of modern advancement in math and science.

> 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-n...

My 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.

It looks like he's asking about the halting problem. I'm not a mathematician, but it looks like he's asking if a machine could be built that could solve all of mathematics in linear or quadratic time.

No, not quite. Roughly speaking, he's asking about the computational complexity of solving problems (producing proofs of statements in first-order predicate logic) with a given bound N on the size of the solution. This is computable becaue the number of solutions (i.e., proofs) of length <= N is finite, and one can in principle just enumerate them all and check. Goedel's question is how the running time of producing a solution of size <= N (or finding that there is no solution of size <= N) grows with N, with the thinking that if no proof of a reasonable size can be found, one might as well not bother looking anymore.

Reply on news.ycombinator.com