16
$\begingroup$

Nisan proved in "Psuedorandom Generators for Space-Bounded Computation", that there exists a pseudo-random generator which "fools" space-bounded computations. Does this construction hold for every oracle (at least for non-adaptive queries) ?

$\endgroup$
18
$\begingroup$

It depends on whether in your definition of the Oracle TM, the oracle query tape is also bounded to be of logarithmic size: if it is bounded then the PRG fools also L^A for any A too, if it is not bounded then A can contain the list of "pseudorandom strings" and thus L^A will not be fooled.

$\endgroup$
  • $\begingroup$ This is true for all pseudo-random generators, however, for example, NW generator does relativizies if we assume hardness against the oracle we want to fool. I was wondering whether we can do something of this kind also for this generator. $\endgroup$ – Sebastian Ben Daniel Oct 17 '10 at 0:24
  • 5
    $\begingroup$ Since this PRG is completely specified (ie not based on some other "hard function f"), it's not clear how to use the oracle in the relativized setting. $\endgroup$ – Noam Oct 17 '10 at 4:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.