com bits aleatórios polilog é em

Considere uma máquina (ou seja, um algoritmo probabilístico que usa espaço de log e polinomialmente muitos bits aleatórios). Sabe-se (Saks-Zhou) que .$BPL$$BPL \subseteq DSPACE(log^{1.5}(n))$

Minha pergunta é sobre uma máquina que usa apenas polilog muitos bits de aleatoriedade. Em um dos artigos de Goldreich, é mencionado de passagem que uma linguagem decidida por tal máquina está realmente em determinista logspace . Mas não consigo encontrar explicações para essa observação em nenhum lugar.$BPL$$BPL$$L$

Por que ele pode ser des randomizado completamente no espaço de registro?

Segue-se a partir deste PRG de Nisan e Zuckerman . Este artigo mostra que, se você tiver um algoritmo que usa espaço e apenas bits aleatórios , o número de bits aleatórios pode ser reduzido para .p o l y ( S ) O ( S $S$$\mathrm{poly}(S)$$O(S)$

Em particular, na configuração que você descreve, temos , portanto, o número de bits aleatórios pode ser reduzido para . Em seguida, podemos derandomizar o algoritmo completamente enumerando todos os possíveis lançamentos de moedas.O ( log n $S = O(\log n)$$O(\log n)$