Czy pseudolosowy generator Nisana relatywizuje się?

16

Nisan udowodnił w „Psuedorandom Generators for Compound-Bounded Computation”, że istnieje pseudolosowy generator, który „oszuka” obliczenia ograniczone w przestrzeni. Czy ta konstrukcja obowiązuje dla każdej wyroczni (przynajmniej w przypadku zapytań nieadaptacyjnych)?

cc.complexity-theory space-bounded derandomization Sebastian Ben Daniel
źródło
Nie potrafię odpowiedzieć na to pytanie, ale chciałem wskazać na pokrewny artykuł zatytułowany „Twardość kontra przypadkowość” ( dx.doi.org/10.1016/S0022-0000(05)80043-1 ), który może okazać się przydatny.
MS Dousti

Odpowiedzi:

18

Zależy to od tego, czy w twojej definicji Oracle TM taśma zapytania Oracle ma również logarytmiczny rozmiar: jeśli jest ograniczona, PRG oszuka także L ^ A dla dowolnego A, jeśli nie jest ograniczona, A może zawierają listę „pseudolosowych ciągów” i dlatego L ^ A nie da się oszukać.

Noam
źródło
Dotyczy to wszystkich generatorów pseudolosowych, jednak na przykład generator NW wykonuje relatywizacje, jeśli założymy twardość względem wyroczni, którą chcemy oszukać. Zastanawiałem się, czy możemy zrobić coś takiego również dla tego generatora.
Sebastian Ben Daniel
5
Ponieważ ten PRG jest całkowicie określony (tj. Nie oparty na jakiejś innej „twardej funkcji f”), nie jest jasne, jak używać wyroczni w relatywizowanym ustawieniu.
Noam