4 ms·
I have a feeling that if someone ever found that P=NP, it wouldn't be game-changing at all, but it would be like a proof that you can express the problem as O(x
by WilliamLP 17y ago
I have a feeling that if someone ever found that P=NP, it wouldn't be game-changing at all, but it would be like a proof that you can express the problem as O(x^2^2^2^2^10,000,000). (Or with the exponent being an even more absurdly large number, of which there are many.)
- smikhanov 17y agoVery unlikely. Very few known efficient algorithms for natural problems have exponents above 3 or 4. If P=NP would be proven, polynomial algorithms for NP-complete problems would likely to follow this "trend".
- WilliamLP 17y agoHave you heard of Grahams number? (http://en.wikipedia.org/wiki/Graham%27s_number http://en.wikipedia.org/wiki/Graham%27s_number) It comes from a legitimate math proof, and it's unimaginably large. Or, I'm reminded of a proof, related to the Goldbach Conjecture, that every even number is the sum of at most 20 primes. There is a lot of precedent in math to find existence proofs for results that are completely useless for finding a practical solution.