tag:blogger.com,1999:blog-3722233.post3743356831833676109..comments2022-05-24T23:04:24.301-05:00Comments on Computational Complexity: What would you do if you showed P=NP? I would reread Factor Man by Matt GinsbergLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-53269968401363728262020-01-14T15:04:56.448-06:002020-01-14T15:04:56.448-06:00I've been wondering about that. What if a P=NP...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.<br /><br />"I wonder how much damage would be done in the transition period from public to private key"<br /><br />But there's no way to retroactively switch to private key. If public key crypto gets broken, it compromises all messages already send.Abigailnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61447129976560296662020-01-14T03:29:19.331-06:002020-01-14T03:29:19.331-06:00I am surprised that you write in your review: &quo...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".<br /><br />I 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 <a href="https://blog.computationalcomplexity.org/2013/10/p-vs-np-is-elementary-no-p-vs-np-is-on.html" rel="nofollow">blog post about P vs NP on Elementary</a>: "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".<br /><br />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"?Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.com