3 ms·
May wish to see https://secure.wikimedia.org/wikipedia/en/wiki/P%3Dnp#Consequences_of_proof https://secure.wikimedia.org/wikipedia/en/wiki/P%3Dnp#Conseq... Bes
by gwern 17y ago
May wish to see https://secure.wikimedia.org/wikipedia/en/wiki/P%3Dnp#Consequences_of_proof https://secure.wikimedia.org/wikipedia/en/wiki/P%3Dnp#Conseq...
Besides the obvious repercussions (some optimization problems get easier, a lot of crypto and I think most every one-way function turn to junk), P=NP does something else: it means mathematicians are unnecessary.
From Godel's letter to von Neumann, where P=NP? was first posed http://rjlipton.wordpress.com/the-gdel-letter/ http://rjlipton.wordpress.com/the-gdel-letter/ :
> One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n, allows one to decide if there is a proof of F of length n (length = number of symbols). Let ψ(F,n) be the number of steps the machine requires for this and let φ(n) = maxF ψ(F,n). The question is how fast φ(n) grows for an optimal machine. One can show that φ(n) ≥ k ⋅ n. If there really were a machine with φ(n) ∼ k ⋅ n (or even ∼ k ⋅ n2), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem.
Being computer users, we should be astonished since we know that everything is math, or can be made math. But here's a restatement from Scott Aaronson http://scottaaronson.com/blog/?p=190 http://scottaaronson.com/blog/?p=190 :
> That said, certainly if P=NP there would be dramatic consequences for AI. For example, you could efficiently find the shortest program that outputs (say) the complete works of Shakespeare or stock market data in a reasonable amount of time. The question is just how much that would do for you — i.e. once you had that short description, could you use it to predict the future or write plays that Shakespeare himself never wrote?
- roundsquare 17y agoI don't think that would really excite most people. Most people probably think mathematicians are largely unnecessary to begin with. Even among people who recognize the value of mathematics, proving new theorems isn't really exciting for them.