O gerador pseudo-aleatório de Nisan se relativiza?

Nisan provou em "Geradores Psico-Aleatórios para Computação Limitada ao Espaço", que existe um gerador pseudo-aleatório que "engana" os cálculos limitados pelo espaço. Essa construção vale para todos os oráculos (pelo menos para consultas não adaptativas)?

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

Não consigo responder a essa pergunta, mas gostaria de apontar para um artigo relacionado intitulado "Dureza versus aleatoriedade" ( dx.doi.org/10.1016/S0022-0000(05)80043-1 ), que você pode achar útil.

MS Dousti 16/10/10

Respostas:

Depende se, em sua definição do Oracle TM, a fita de consulta do oracle também é delimitada para ter tamanho logarítmico: se for delimitada, o PRG também engana L ^ A para qualquer A também, se não delimitada, A pode contém a lista de "seqüências pseudo-aleatórias" e, portanto, L ^ A não será enganado.

Noam
fonte

Isso é verdade para todos os geradores pseudo-aleatórios; no entanto, por exemplo, o gerador NW faz relatividade se assumirmos dureza contra o oráculo que queremos enganar. Fiquei me perguntando se podemos fazer algo desse tipo também para este gerador.

Sebastian Ben Daniel

Como esse PRG é completamente especificado (ou seja, não é baseado em outra "função difícil f"), não está claro como usar o oráculo no cenário relativizado.

Noam