Relativiert Nisans Pseudo-Zufallsgenerator?

Nisan hat in "Pseudozufallsgeneratoren für weltraumgebundene Berechnungen" bewiesen, dass es einen Pseudozufallsgenerator gibt, der weltraumgebundene Berechnungen "täuscht". Gilt diese Konstruktion für jedes Orakel (zumindest für nicht adaptive Abfragen)?

cc.complexity-theory space-bounded derandomization Sebastian Ben Daniel
quelle

Ich kann diese Frage nicht beantworten, wollte aber auf einen Artikel mit dem Titel "Hardness vs. Randomness" ( dx.doi.org/10.1016/S0022-0000(05)80043-1 ) verweisen , den Sie vielleicht nützlich finden.

MS Dousti 16.10.10

Antworten:

Es hängt davon ab, ob in Ihrer Definition von Oracle TM das Orakel-Abfrageband auch eine logarithmische Größe hat: Wenn es begrenzt ist, täuschen die PRG-Narren auch über L ^ A, wenn es nicht begrenzt ist, kann A enthalten die Liste der "Pseudozufälligen Zeichenfolgen" und somit wird L ^ A nicht getäuscht.

Noam
quelle

Dies gilt für alle Pseudozufallsgeneratoren. Der NW-Generator führt jedoch beispielsweise Relativisierungen durch, wenn wir eine Härte gegen das Orakel annehmen, das wir zum Narren halten wollen. Ich habe mich gefragt, ob wir so etwas auch für diesen Generator tun können.

Sebastian Ben Daniel

Da diese PRG vollständig spezifiziert ist (dh nicht auf einer anderen "harten Funktion f" basiert), ist es nicht klar, wie das Orakel in der relativierten Einstellung verwendet wird.

Noam