Lance has often said (and also in this) that if P=NP that would be great for the world: much more efficient ways to build things, science could be done better, etc, and that is much more important than that modern crypto would no longer work. We now have the technology to do private key really well--- like a thumb drive that has a billion bits for 1-time pads.
I agree that the world would be better off in some ways, I wonder how much damage would be done in the transition period from public to private key. Would the world recover enough to reap the benefits of P=NP?
First think of what YOU would do if you showed P=NP (and lets assume your algorithm is either reasonable or could be made reasonable with some time and effort).
The novel Factor Man is about what someone who has solved P=NP does. I won't tell you how it goes, but they deal with the issue intelligently. So if I solved P=NP then I would first re-read it, and think through if I would do that, or modify what is done, or what. Its a good start.
I reviewed the book in SIGACT News or you can read my review here
On a slightly diff note, here is the latest argument I've heard for why P=NP:
Planar 2-coloring is in P
Planar 4-coloring is in P
So
Planar 3-coloring should be in P.
This was said by a very good math/cs ugrad at UMCP. I do not know if he was kidding.
I am surprised that you write in your review: "just know that if P=NP then (1) all known crypto systems can be broken, (2) given enough warning people can change those systems to hopefully not be broken".
ReplyDeleteI guess what you mean by "change those systems" is to switch to "private key", whatever you meant by that when you mentioned in point 4 in your blog post about P vs NP on Elementary: "As Lance has pointed out in his book if P=NP then the benefits for society are GINORMOUS, and would dwarf the relatively minor problem of having to switch to private key".
From my perspective, if you switch to "private key", the vulnerability will be in how you distribute that "private key". If you plan to use quantum protocols for that, then it would be more honest to say "switch to quantum protocols" instead of saying "switch to private key". Or do you have something more "classical" practical in mind when you talk about "private key"?
I've been wondering about that. What if a P=NP proof isn't constructive, that is, it doesn't provide a method to find polynomial algorithms, it only shows that there are such algorithms. Or if it turns out polynomial algorithms exists, but we can't do better than O(n^k) for some very large k. Both cases would still be huge breakthroughs, but they may not have a big impact on the world.
ReplyDelete"I wonder how much damage would be done in the transition period from public to private key"
But there's no way to retroactively switch to private key. If public key crypto gets broken, it compromises all messages already send.