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 ) ) .
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.
¿Por qué se puede desrandomizar completamente en el espacio de registro?