JoshuaZ comments on The Curve of Capability - Less Wrong

18 Post author: rwallace 04 November 2010 08:22PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (264)

You are viewing a single comment's thread. Show more comments above.

Comment author: JoshuaZ 05 November 2010 09:25:18PM 3 points [-]

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.

Comment author: Douglas_Knight 06 November 2010 01:23:49AM 1 point [-]

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.