Hacker News Reader

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

View on HN

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

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.

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.

Theory often proves fruitful in unexpected ways.

Reply on news.ycombinator.com