# Suppose P = BPP; Pseudorandom Generators vs NP Adversary

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.)

Question:

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

Thanks!

[Context: reduced some open problem to this.]

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

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