com bits aleatórios polilog é em

8

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 .BPLBPLDSPACE(log1.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.BPLBPLL

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

BharatRam
fonte

Respostas:

11

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 )Spoly(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(logn)O(logn)

Ou Meir
fonte