MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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