¿El generador pseudoaleatorio de Nisan se relativiza?

16

Nisan demostró en "Generadores psuedoraaleatorios para la computación limitada al espacio", que existe un generador pseudoaleatorio que "engaña" las computaciones limitadas al espacio. ¿Esta construcción es válida para cada oráculo (al menos para consultas no adaptativas)?

cc.complexity-theory space-bounded derandomization Sebastian Ben Daniel
fuente
No puedo responder a esta pregunta, pero quería señalar un artículo relacionado titulado "Dureza vs. Aleatoriedad" ( dx.doi.org/10.1016/S0022-0000(05)80043-1 ), que puede serle útil.
MS Dousti

Respuestas:

18

Depende de si en su definición de Oracle TM, la cinta de consulta oracle también está limitada a un tamaño logarítmico: si está limitada, el PRG también engaña a L ^ A para cualquier A también, si no está limitado, entonces A puede contiene la lista de "cadenas pseudoaleatorias" y, por lo tanto, L ^ A no se dejará engañar.

Noam
fuente
Esto es cierto para todos los generadores pseudoaleatorios, sin embargo, por ejemplo, el generador NW hace relativizaciones si asumimos dureza contra el oráculo que queremos engañar. Me preguntaba si podemos hacer algo de este tipo también para este generador.
Sebastian Ben Daniel
55
Dado que este PRG está completamente especificado (es decir, no se basa en alguna otra "función difícil f"), no está claro cómo usar el oráculo en la configuración relativizada.
Noam