Tuesday, August 10, 2010

P != NP

Tom Corbett, Space Cadet!
Huh? If this has really been proven, just thinking out loud here, then the likelihood that Public Key Cryptography actually is secure has gone wa-a-ay up.

Personally, I fall into the pessimism camp, that P = NP, and Public Key Cryptography is not only easy to crack but has been cracked already by the NSA. This would imply that even the best PKC implementations reduce to far simpler methods easy to waltz through.

P means decidable, as in, it's pretty easy to tell who won a game of Go.

NP means nearly impossible to play winning Go all the time.

If P != NP, that corresponds to Go as you know it. Easy to decide the winner, hard to become a winner.

P = NP may feel like wishful thinking, but it might actually correspond to reality if, e.g., some algorithm can be applied to a game of Go such that the result computed is a (likely) win. Curiously, this is the situation that is appearing in computer Go, when algorithms use Monte-Carlo methods (whatever that means.) Sylvain Gelly's Go-playing computer program is a good example of the counterintuitive result.

Proof one way or another is worth a million bucks.

P = NP implies Summertime, when the living is easy. It means a problem may be harder than we (and cats, bats and slime molds) can solve, but it does not outlaw a solution by dumb luck, evolution or alien intelligence. An improvable world, that is. I like that, although I could be wrong.

Oh, well.  Back to my corn flakes...

Labels: ,


Post a Comment

Subscribe to Post Comments [Atom]

<< Home