News for hackers. Stuff that matters.
Re:P vs. NP for Dummies by pvg on Sunday August 15, 2010 @02:29PM (#1605609)
"The short answer is: the biggest unsolved problem of theoretical computer science, and one of the deepest questions ever asked by human beings!"

presumably, 'reading' is one of those more useful things that are worth learning, as well.

Re:P vs. NP for Dummies by amichail on Sunday August 15, 2010 @05:14PM (#1605952)
But assuming P!=NP, it's resolution will probably have very little impact on the world.
Re:P vs. NP for Dummies by waqf on Sunday August 15, 2010 @06:18PM (#1606110)
That's (again, probably) not true, although none of the recent flurry of blog posts have explained why not (possibly because it's hard to make this convincing if you're not familiar with mathematical research).

The point is that solutions to such problems as this do not exist in a vacuum: even with the million-dollar incentive for solving the particular stated problems we do not expect that they will be solved without building a network of related sub-theories and sub-theorems, reusable tools which will also help with solving future problems which we don't yet even know enough to formulate.

Fermat's Last Theorem was a good example of this: nobody cares about sums of nth powers, but everybody cares about the Mordell conjecture, Taniyama–Shimura–Weil conjecture etc. which were proved along the way. FLT itself is just a line in the sand to illustrate how far we've come since 1637.

Re:P vs. NP for Dummies by amichail on Sunday August 15, 2010 @06:31PM (#1606142)
Is it likely that a proof of P!=NP will give insight into designing more efficient algorithms? Or mostly insight into proving other lower bounds?
Re:P vs. NP for Dummies by eru on Sunday August 15, 2010 @10:01PM (#1606557)
Perhaps we could get new upper bounds out of it. Or---perhaps the eventual proof will establish a link between hitherto unrelated areas of mathematics. This link could be used to transform whole classes of theorems and proof structures / ideas from one field to another.
Re:P vs. NP for Dummies by pvg on Sunday August 15, 2010 @07:26PM (#1606244)
I think his argument is that such a proof would represent a significant advance in human knowledge. At its time of origin, the special theory of relativity didn't give anyone nicer cars, either.
Re:P vs. NP for Dummies by jongraehl on Monday August 16, 2010 @12:46AM (#1606868)
I agree, except that it would free up brainpower to work on other problems, and that it would allow more confidence in cryptosystems that rely on an NP-hard problem being exponential time (but I don't think factoring a large product of two primes like could break RSA, is NP-hard).

A resolution P=NP would likely have a huge practical effect, but most people don't expect that to happen.