O RNC uniforme está contido no espaço polylog?

O NC uniforme de espaço de log está contido no espaço polilog determinístico (às vezes escrito em PolyL). O RNC com espaço de log uniforme também está nesta classe? A versão aleatória padrão do PolyL deve estar em PolyL, mas não vejo que o RNC (uniforme) esteja em PolyL randomizado.

A dificuldade que vejo é que, no RNC, o circuito pode "olhar os bits aleatórios" o quanto quiser; ou seja, as entradas aleatórias podem ter fanout arbitrário. Mas, na versão aleatória do PolyL, não é como se você tivesse uma fita de bits aleatórios que pode ver o quanto quiser; em vez disso, você só pode jogar uma moeda a cada passo.

Obrigado!

Talvez a maioria das pessoas pense que (ou mesmo que ), mas sou cético quanto a isso (consulte a segunda parte de minha resposta abaixo). Se está realmente contido em , também está contido em (mais especificamente, em por pesquisa exaustiva).$\mathsf{RNC}\subseteq \mathsf{DSPACE(polylog)}$$\mathsf{RNC}=\mathsf{NC}$$\mathsf{RNC}$$\mathsf{DSPACE(polylog)}$$\mathsf{NTIME(2^{polylog})}$$\mathsf{DTIME(2^{polylog})}$

Valentine Kabanets me explicou o seguinte argumento (folclore) de seu artigo com Russell Impagliazzo, que explica por que é improvável.$\mathsf{RNC} \subseteq \mathsf{NTIME(2^{polylog})}$

Teorema: Se , então não é computável por circuitos booleanos de tamanho (isto é, sub- maxsize por Shannon; irrelevante, mas veja Lupanov quanto à tensão) ou Permanente não é computável por fórmulas aritméticas (sem divisão) sobre de tamanho quase-polinomial.$\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$$\mathsf{NEXP}$$o(2^n/n)$${\mathbb Z}$

Prova: assuma . Se o Permanent tiver uma fórmula de tamanho quase-polinomial, podemos adivinhar e verificar essa fórmula para o permanente usando um testador de identidade polinomial no tempo quase-polinomial por suposição. Isso coloca Permanente em .$\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$$\mathsf{NTIME(2^{polylog})}$

Pelo teorema de Toda, também está em . Por preenchimento, a versão de tempo linear-exponencial de também está em . Portanto, a versão linear-exponencial de possui um circuito de tamanho (isto é, submax). Mas, por um argumento simples de diagonalização, pode-se mostrar que a versão exponencial linear de requer tamanho máximo de circuito, o que é uma contradição (a propósito, essa é uma variante de uma pergunta de nível médio para uma complexidade de nível de pós-graduação) Claro, tudo bem, talvez provar que exija circuitos de tamanho máximo seja mais simples). QED.$\Sigma_2$Σ 5 N E X P Σ 5 o ( 2 n / n ) Σ 5 E X P S P A C $\mathsf{NTIME(2^{polylog})}$$\Sigma_5$$\mathsf{NEXP}$$\Sigma_5$$o(2^n/n)$$\Sigma_5$$\mathsf{EXPSPACE}$

Agora a direção impopular.

Já sabemos que a aleatoriedade lida muitas vezes pode fazer algo não óbvio. Um exemplo interessante pode ser encontrado em " Tornando o não determinismo inequívoco ", de Reinhardt e Allender (eles o declaram em termos de não uniformidade, mas, em princípio, trata-se de usar a aleatoriedade de leitura muitas vezes). Outro exemplo interessante (menos diretamente relacionado) é " Randomness Buys Depth for Approximate Counting ", de Emanuele Viola. Acho que tudo o que estou dizendo é que não ficaria surpreso se a derandomização de não fosse o que a maioria das pessoas espera que seja.$\mathsf{RNC}$

(Também existem alguns outros artigos, como o maravilhoso artigo de Noam Nisan sobre aleatoriedade de leitura única versus leitura múltipla, que mostra como comprar erro de dois lados com erro de um lado.)

A propósito, entender como construir PRGs enganando modelos de computação limitados ao espaço com múltiplos acessos à sua entrada (por exemplo, comprimentos lineares Bps) também está muito relacionado a essa questão.

- Periklis