I've read that one too, but I don't particularly like it. P=NP implies only that all problems which can be verified in polynomial time can also be solved in polynomial time, not necessarily that it can be solved as quickly, nor that it can be solved easily.

Perhaps writing a piece of music is also done in polynomial time, but it requires more training (more advanced algorithm)? Or, perhaps, the time complexity is x^3 for writing, instead of x for appreciating.

Agreed, it is bit sensationalist. But what if someone proves it and then we realize that even though it can be done in polynomial time, there's some other constraint (like "x^N but N has to be super big") that renders the result impractical?

I think once someone proves it, it will be obvious in hindsight as a lot of people are just ignoring the isomorphisms in nature.

Yup, doing a big of handwavy math also demonstrates this: You are comparing something like x^N - x^M with 2^x - x^M. The second will always grow big rapidly, while the first could stay small, but it can also grow arbitrarily large. In fact, it is bound to do so for N > M and it will do so quite rapidly if N >> M.

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

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.

> if it were, you could write a piece of music as easily as you could appreciate it.

Yea, but maybe it would still be exactly 1.000.000 times as hard.

Meaning you wasted a shit ton of time trying to prove something obvious :)

Well no, we've destroyed constant factors of greater than a million before.

This is also a bad analogy because human beings tend to be extremely good at solving, or at least approximating close solutions to, NP-complete problems (on small instances).

When I'm drifting off to sleep, I frequently hallucinate polyphonic songs. Real time composition. P=NP? :)

That is a brilliant way of putting it, thanks!