Actually, to add a word of caution to these answers saying that P = NP would mean public key encryption is insecure, and all famous problems with short proofs would be quickly proved - actually that doesn't follow at all.
Polynomial time doesn't tell you anything about the coefficients of the polynomial. What if the coefficients are all of the order of 10^(10^10) (1 followed by 10,000,000,000 zeros) or higher?
Even a solution in linear time would be of no practical use at all if the coefficient is huge.
To take an example, suppose someone found a solution of the traveling salesman problem which requires at most 10^(10^10) * n steps, where n is the number of cities?
That's a linear time solution, and if anyone found such a solution it would prove P = NP, (because it is an NP complete problem) - they'd be immediately famous - but it's not a practical solution.
It wouldn't be at all astonishing if it came up with really huge coefficients like that. Maybe even coefficients that need Knuth's up-arrow notation (similarly to Graham's number). Then it would still be a theoretically very interesting result, even if the coefficients are too large to be expressed with exponential notation.
Of course many mathematicians would then work away at the proof to try to reduce the size of the coefficients - but no a priori reason why they have to succeed in reducing them to the extent that it becomes practically useful.
Polynomial time doesn't tell you anything about the coefficients of the polynomial. What if the coefficients are all of the order of 10^(10^10) (1 followed by 10,000,000,000 zeros) or higher?
Even a solution in linear time would be of no practical use at all if the coefficient is huge.
To take an example, suppose someone found a solution of the traveling salesman problem which requires at most 10^(10^10) * n steps, where n is the number of cities?
That's a linear time solution, and if anyone found such a solution it would prove P = NP, (because it is an NP complete problem) - they'd be immediately famous - but it's not a practical solution.
It wouldn't be at all astonishing if it came up with really huge coefficients like that. Maybe even coefficients that need Knuth's up-arrow notation (similarly to Graham's number). Then it would still be a theoretically very interesting result, even if the coefficients are too large to be expressed with exponential notation.
Of course many mathematicians would then work away at the proof to try to reduce the size of the coefficients - but no a priori reason why they have to succeed in reducing them to the extent that it becomes practically useful.
About the Author
Robert Walker
Writer of articles on Mars and Space issues - Software Developer of Tune Smithy, Bounce Metronome etc.Studied at Wolfson College, Oxford
Lives in Isle of Mull
4.8m answer views110.3k this month
Top Writer2017, 2016, and 2015
Published WriterHuffPost, Slate, and 4 moreHuffPost, Slate, Forbes, Newsweek, Business Insider, and Science 2.0