re: Thoughts on the P versus NP problem?

quote:

---

On the other hand, it opens up a realm of possibilities of previously insurmountable computational problems in biology, economics, etc. becoming easily solvable.

---

Right, but holy hell would it wreak havoc.

I think an affirmative P = NP proof would prove that one-way functions don't exist, which would pretty much mean that none of our internet data is secure.

So, goodbye to online banking, online shopping, and cryptocurrency. We'd have to completely reinvent how data is encrypted.

I thought this was another thread about dudes in womens sports.

Not a mathematician or computer scientist

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?

I guess I'm separating the academic potential that P could = NP and the practical real world potential of actually solving NP problems. So could we prove P=NP, but still have encryption safe?

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.

quote:

---

Is it possible to prove P=NP but still be practically unable to solve NP problems?

---

Not really. Those problems wouldn't be unsolvable for long.

If you prove P = NP, then it means all problems in NP can be solved quickly. It would just be a matter of time before someone finds a fast algorithm for these problems.

quote:

---

I guess I'm separating the academic potential that P could = NP and the practical real world potential of actually solving NP problems. So could we prove P=NP, but still have encryption safe?

---

Like the OP said, it would be a major breakthrough since it would solve some real problems, but we'd have to reinvent some cryptographic algorithms. Anything that relies on a P =/= NP assumption would have to get tossed out.

I definitely thought this was another thread about trannies in women's sports.