Le générateur pseudo-aléatoire de Nisan se relativise-t-il?

Nisan a prouvé dans "Générateurs aléatoires pour le calcul délimité par l'espace", qu'il existe un générateur pseudo-aléatoire qui "trompe" les calculs délimités par l'espace. Cette construction est-elle valable pour chaque oracle (au moins pour les requêtes non adaptatives)?

cc.complexity-theory space-bounded derandomization Sebastian Ben Daniel
la source

Je ne peux pas répondre à cette question, pourtant je voulais pointer vers un article connexe intitulé "Dureté contre aléatoire" ( dx.doi.org/10.1016/S0022-0000(05)80043-1 ), que vous pourriez trouver utile.

MS Dousti

Réponses:

Cela dépend si, dans votre définition d'Oracle TM, la bande de requête Oracle est également limitée à une taille logarithmique: si elle est limitée, le PRG trompera également L ^ A pour tout A également, s'il n'est pas limité, alors A peut contiennent la liste des "chaînes pseudo-aléatoires" et donc L ^ A ne sera pas dupe.

Noam
la source

Cela est vrai pour tous les générateurs pseudo-aléatoires, cependant, par exemple, le générateur NW fait des relativisations si nous supposons la dureté contre l'oracle que nous voulons tromper. Je me demandais si nous pouvions faire quelque chose de ce genre également pour ce générateur.

Sebastian Ben Daniel

Étant donné que ce PRG est complètement spécifié (c'est-à-dire qu'il n'est pas basé sur une autre "fonction dure f"), il n'est pas clair comment utiliser l'oracle dans le paramètre relativisé.

Noam