5 ms·
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 appreci
by mion 13y ago
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.
Also, I can't imagine the answer to something as fundamental as this coming out of a hacky solution. There's probably a more elegant, natural way to prove it. And by natural I mean maybe they should start looking outside Turing's theory.
- Trufa 13y agoThat is a brilliant way of putting it, thanks!
- hansbo 13y agoI'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.
- mion 13y agoAgreed, 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.
- tetha 13y agoYup, 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.
- Tmmrn 13y ago> 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.
- biofox 13y agoWhen I'm drifting off to sleep, I frequently hallucinate polyphonic songs. Real time composition. P=NP? :)
- Houshalter 13y ago>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.
- mion 13y agoThis 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".
- dllthomas 13y agoSay 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.
- j2kun 13y agoThis 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).