Derandomização uniforme de classes de complexidade de circuitos

Deixe ser uma classe de complexidade e BP- C ser o homólogo randomizado de C definida da mesma maneira como o BPP é definida com relação a P . Mais formalmente, fornecemos polinomialmente muitos bits aleatórios e aceitamos uma entrada se a probabilidade de aceitação for superior a $\mathcal{C}$$\textrm{BP-}\mathcal{C}$$\mathcal{C}$$\textrm{BPP}$$\textrm{P}$ .$\frac{2}{3}$

Em um post anterior , perguntei se era sabido se a igualdade existe entre e BP- C para C uma classe de complexidade de circuitos. A resposta é sim para todas as classes de complexidade expressivas o suficiente para calcular a Maioria e para AC 0 por algum outro motivo. No entanto, esses resultados não são uniformes e eu gostaria de saber:$\mathcal{C}$$\textrm{BP-}\mathcal{C}$$\mathcal{C}$$\textrm{AC}^0$

1. As versões uniformes desses resultados são estudadas ou conhecidas? Algum resultado parcial?

2. Elas implicam conjecturas de longa data?

Acredito que a des aleatorização uniforme de é exatamente P = BPP, portanto, espero que a resposta seja "sim", mas é menos claro para mim o que implicaria a desalerização uniforme de pequenas classes na hierarquia NC .$\textrm{P}/\textrm{poly}$$\textrm{P}=\textrm{BPP}$$\textrm{NC}$

A classe uniforme-RNC tem sido muito estudada. É um problema em aberto se uniforme-RNC = uniforme-NC. NC uniforme (R) corresponde a PRAMs (randomizadas) com muitos processadores polinomialmente e tempo de execução polilogarítmico (consulte o Manual de Teoria da Computação Teórica, Vol. A). Portanto, a questão é se todos os algoritmos paralelos aleatórios eficientes podem ser des randomizados.

Como o teste de identidade determinante simbólica está no RNC uniforme, o RNC derandomizing implica limites inferiores do circuito pelos resultados de Kabanets & Impagliazzo (Computational Complexity, 13 (1-2), páginas 1-46, 2004).

Um caso especial importante é a questão de saber se podemos computar combinações perfeitas no NC uniforme. Existem vários algoritmos paralelos aleatórios conhecidos, mas não sabemos se existe um determinístico. Recentemente, Fenner, Gurjar e Thierauf (STOC 2016) mostraram que podemos computar combinações perfeitas em gráficos bipartidos por circuitos uniformes de profundidade polilogarítmica e tamanho quase-polinomial.