3 ms·

It's funny because in the average CS degree the P=NP problem isn't even covered (my sample at least all learned about it online). I don't know if I know a conc

It's funny because in the average CS degree the P=NP problem isn't even covered (my sample at least all learned about it online). I don't know if I know a concrete example of a specific way the world would differ either. Maybe quicker routing, cancer algorithm solving, simulations, broken encryptions that kind of stuff?

donaq 17y ago
Really? Where did you get your CS degree? I thought complexity theory is an essential part of any algorithms module, and an algorithms module is in turn an essential part of any CS degree. I'd hate to have to hire a CS grad who hasn't taken a class in algorithms. Are you sure you didn't just not turn up that day? >:)
- simonista 17y ago
  To add a personal experience to what your saying, it's been taught in a fair amount of detail in two of my classes (at the University of Utah) and has been glossed over in a few others.
- nopassrecover 17y ago
  We did comprehensive work on algorithm complexity/data structures etc. But the NP Complete problem itself was never even touched on beyond a side reference to the travelling salesman problem at best.
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 ago
  I 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.

donaq 17y ago

Really? Where did you get your CS degree? I thought complexity theory is an essential part of any algorithms module, and an algorithms module is in turn an essential part of any CS degree. I'd hate to have to hire a CS grad who hasn't taken a class in algorithms. Are you sure you didn't just not turn up that day? >:)

simonista 17y ago
To add a personal experience to what your saying, it's been taught in a fair amount of detail in two of my classes (at the University of Utah) and has been glossed over in a few others.
nopassrecover 17y ago
We did comprehensive work on algorithm complexity/data structures etc. But the NP Complete problem itself was never even touched on beyond a side reference to the travelling salesman problem at best.

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 ago
I 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.