Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose P = BPP.

Then we know there exist pseudorandom number generators vs P.

Suppose the adversary is NP.

Now, any pseudorandom number generator that only uses P will fail. (Since NP can invert one-way functions, and thus break any pseudorandom number generator based on them.)


How powerful do we have to allow the generator to be (EXP?) in order to generate a pseudorandom sequence that can fool NP?


[Context: reduced some open problem to this.]

[EDIT: Adversary does NOT have an NP oracle. Adversary is NP]

share|improve this question
All these acornyms are standard in complexity theory. See Arora/Barak for example. –  circuits2 Oct 5 '11 at 17:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.