News for hackers. Stuff that matters.
Re:P = NP by Houshalter on Wednesday December 04, 2013 @10:40AM (#6847559)
>The best intuition I've read that P = NP can't possibly turn out to be true, is that if it were, you could write a piece of music as easily as you could appreciate it.

Your intuition isn't always correct, there is algorithmic music that can sort of do this already. And just because it seems weird doesn't mean it's impossible, just that no one has figured it out yet.

Re:P = NP by mion on Wednesday December 04, 2013 @11:30AM (#6847970)
This is why I said intuition. What I meant is that N = NP would suggest, for instance, that the amount of effort needed to appreciate a brilliant piece of music (e.g. Mozart, not any music) is in the same "space" of the amount of effort needed to create it.

You can find many examples of things in nature that are "hard to solve" yet "easy to verify".

Re:P = NP by dllthomas on Wednesday December 04, 2013 @11:36AM (#6848005)
Say we find an algorithm to solve SAT in O(x^1000). P would equal NP, and yet the set of problems we currently label NP-complete might still be substantially harder to solve than to verify.
Re:P = NP by mion on Wednesday December 04, 2013 @12:27PM (#6848445)
Thus rendering the theory rather "useless". What some people are trying to do by attempting to prove N = NP (and this is the main source of criticism), is to find a way to "hack" nature.
Re:P = NP by dllthomas on Wednesday December 04, 2013 @12:59PM (#6848725)
Theory often proves fruitful in unexpected ways.