3 ms·
Very 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-comp
by smikhanov 17y ago
Very 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.