I estimate about a 1% chance that P=NP is provable in ZFC, around a 2% chance that P=NP is undecideable in ZFC (this is a fairly recent update. This number used to be much smaller. I am willing to discuss reasons for it if anyone cares.) and a 97% chance that P !=NP.
I’m not sure I’m parsing that correctly. Is that 2% for undecidable or undecidable+true? Don’t most people consider undecidability evidence against?
But if P=NP in a practical way, … Many crypto systems not just RSA will be vulnerable.
All crypto systems would be vulnerable. At least, all that have ever been deployed on a computer.
I’m not sure I’m parsing that correctly. Is that 2% for undecidable or undecidable+true? Don’t most people consider undecidability evidence against?
2% is undecidable in general. Most of that probability mass is for “There’s no polynomial time solver for solving an NP complete problem but that is not provable in ZFC” (obviously one then needs to be careful about what one means by saying such a thing doesn’t exist, but I don’t want to have to deal with those details). A tiny part of that 2% is the possibility that there’s a polynomial time algorithm for solving some NP complete problem but one can’t prove in ZFC that the algorithm is polynomial time. That’s such a weird option that I’m not sure how small a probability for it, other than “very unlikely.”
All crypto systems would be vulnerable. At least, all that have ever been deployed on a computer.
Actually, no. There are some that would not. For example, one-time pads have been deployed on computer systems (among other methods using USB flash drives to deliver the secure bits.) One-time pads are provably secure. But all public key cryptography would be vulnerable, which means most forms of modern crypto.
I forgot about one-time pads, which certainly are deployed, but which I don’t think of as crypto in the sense of “turning small shared secrets into large shared secrets.” My point was that breaks not just public-key cryptography, but also symmetric cryptography, which tends to be formalizable as equivalent to one-way functions.
I’m not sure I’m parsing that correctly. Is that 2% for undecidable or undecidable+true? Don’t most people consider undecidability evidence against?
All crypto systems would be vulnerable. At least, all that have ever been deployed on a computer.
2% is undecidable in general. Most of that probability mass is for “There’s no polynomial time solver for solving an NP complete problem but that is not provable in ZFC” (obviously one then needs to be careful about what one means by saying such a thing doesn’t exist, but I don’t want to have to deal with those details). A tiny part of that 2% is the possibility that there’s a polynomial time algorithm for solving some NP complete problem but one can’t prove in ZFC that the algorithm is polynomial time. That’s such a weird option that I’m not sure how small a probability for it, other than “very unlikely.”
Actually, no. There are some that would not. For example, one-time pads have been deployed on computer systems (among other methods using USB flash drives to deliver the secure bits.) One-time pads are provably secure. But all public key cryptography would be vulnerable, which means most forms of modern crypto.
I forgot about one-time pads, which certainly are deployed, but which I don’t think of as crypto in the sense of “turning small shared secrets into large shared secrets.” My point was that breaks not just public-key cryptography, but also symmetric cryptography, which tends to be formalizable as equivalent to one-way functions.