ciphergoth comments on Who thinks quantum computing will be necessary for AI? - Less Wrong

4 Post author: ChrisHallquist 28 May 2013 10:59PM

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

Comments (101)

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

Comment author: ciphergoth 29 May 2013 07:54:24PM *  13 points [-]

You don't sound like you're now much less confident you're right about this, and I'm a bit surprised by that!

I got the ladder down so I could get down my copy of Goldreich's "Foundations of Cryptography", but I don't quite feel like typing chunks out from it. Briefly, a pseudorandom generator is an algorithm that turns a small secret into a larger number of pseudorandom bits. It's secure if every distinguisher's advantage shrinks faster than the reciprocal of any polynomial function. Pseudorandom generators exist iff one-way functions exist, and if one-way functions exist then P != NP.

If you're not familiar with PRGs, distinguishers, advantage, negligible functions etc I'd be happy to Skype you and give you a brief intro to these things.

Comment author: Wei_Dai 29 May 2013 09:00:55PM *  10 points [-]

If you're not familiar with PRGs, distinguishers, advantage, negligible functions etc I'd be happy to Skype you and give you a brief intro to these things.

There are also intros available for free on Oded Goldreich's FoC website.

Here's my simplified intuitive explanation for people not interested in learning about these technical concepts. (Although of course they should!) Suppose you're playing rock-paper-scissors with someone and you're using a pseudorandom number generator, and P=NP, then your opponent could do the equivalent of trying all possible seeds to see which one would reproduce your pattern of play, and then use that to beat you every time.

In non-adversarial situations (which may be what Eliezer had in mind) you'd have to be pretty unlucky if your cognitive algorithm or environment happens to serve as a distinguisher for your pseudorandom generator, even if it's technically distinguishable.

Comment author: Eliezer_Yudkowsky 29 May 2013 09:44:46PM -1 points [-]

Okay, makes sense if you define "distinguishable from random" as "decodable with an amount of computation polynomial in the randseed size".

EDIT: Confidence is about standard cryptographically strong randomness plus thermal noise being sufficient to prevent expected correlation with bits playing a functional role, which is all that could possibly be relevant to cognition.

Comment author: ciphergoth 30 May 2013 06:02:56AM 4 points [-]

Decoding isn't the challenge; the challenge is to make a guess whether you're seeing the output of the PRG or random output. Your "advantage" is

Adv_PRG[Distinguisher] = P(Distinguisher[PRG[seed]] = "PRG") - P(Distinguisher[True randomness] = "PRG")

Comment author: JoshuaZ 30 May 2013 01:29:57AM *  4 points [-]

Note that this is standard notation when one discusses pseudorandom generators. Hence Ciphergoth's comment about "the usual definitions."

Comment author: Eliezer_Yudkowsky 30 May 2013 03:04:16AM 0 points [-]

(Nods.)