3 ms·
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 pol
by hansbo 13y ago
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.
- 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.