con bits al azar polylog está en

8

Considere una máquina (es decir, un algoritmo probabilístico que usa espacio de registro y polinomialmente muchos bits aleatorios). Se sabe (Saks-Zhou) que B P L D S P A C E ( l o g 1.5 ( n ) ) .siPAGSLsiPAGSLreSPAGSUNACmi(losol1,5(norte))

Mi pregunta es sobre una máquina que usa solo polylog muchos bits de aleatoriedad. En uno de los documentos de Goldreich, se menciona de pasada que un lenguaje decidido por una máquina B P L de este tipo está en el espacio de registro L determinista . Pero no puedo encontrar ninguna explicación de este comentario en ninguna parte.siPAGSLsiPAGSLL

¿Por qué se puede desrandomizar completamente en el espacio de registro?

BharatRam
fuente

Respuestas:

11

Se desprende de este PRG de Nisan y Zuckerman . Este trabajo muestra que si tiene un algoritmo que utiliza el espacio y sólo p o l y ( S ) bits aleatorios, entonces el número de bits aleatorios se pueden disminuir a O ( S ) .Spagsoly(S)O(S)

S=O(Iniciar sesiónnorte)O(Iniciar sesiónnorte)

O meir
fuente