re: Thoughts on the P versus NP problem?

quote:

---

Would proving P=NP provide any information toward actually solving NP problems? Is it possible to prove P=NP but still be practically unable to solve NP problems?

---

An N=NP theorem would undoubtably provide a blueprint for converting all NP problems to P. In fact, that’s probably how it would be solved if it is ever proven. The lucky mathematician would stumbled upon an insight that irrefutably demonstrated that an NP problem can be written out as a P problem and solved just as easily.

Edit: This is how Fermat’s Last Theorem was proven. It was realized that the equation a^n + b^n = c^n would have to be elliptical, but if all elliptical equations are modular (as Taniyama-Shimura conjectured), the exponent could never be greater than 2. That’s how Andrew Wiles solved the theorem. He didn’t tackle Fermat’s Last Theorem directly. He took an alternative path and tackled Taniyama-Shimura, which gave FML for free.


So to answer your question, the theorem wouldn’t automatically provide ways of breaking encryption, but it would provide the blueprint and the first, and hardest stepping stone, to doing so.