# Does Nisan's pseudo-random generator relativize?

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

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.

• 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. – Sebastian Ben Daniel Oct 17 '10 at 0:24
• 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. – Noam Oct 17 '10 at 4:17