Wei_Dai comments on Who thinks quantum computing will be necessary for AI? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (101)
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.