Dérandomisation uniforme des classes de complexité des circuits

Que soit une classe de complexité et BP- C la contrepartie aléatoire de C défini de la même manière que BPP est défini par rapport à P . Plus formellement, nous fournissons polynomialement de nombreux bits aléatoires et nous acceptons une entrée si la probabilité d'accepter est supérieure à $\mathcal{C}$$\textrm{BP-}\mathcal{C}$$\mathcal{C}$$\textrm{BPP}$$\textrm{P}$ .$\frac{2}{3}$

Dans un post précédent , j'ai demandé si l'on savait si l'égalité se maintenait entre et BP- C pour C une classe de complexité de circuit. La réponse est oui pour toutes les classes de complexité suffisamment expressives pour calculer la majorité et pour AC 0 pour une autre raison. Ces résultats ne sont cependant pas uniformes et j'aimerais savoir:$\mathcal{C}$$\textrm{BP-}\mathcal{C}$$\mathcal{C}$$\textrm{AC}^0$

1. Des versions uniformes de ces résultats sont-elles étudiées ou connues? Des résultats partiels?

2. Impliquent-ils une conjecture de longue date?

Je crois que la dérandomisation uniforme de est exactement P = BPP, donc je m'attends à ce que la réponse soit "oui", mais il est moins clair pour moi ce que la dérandomisation uniforme de petites classes au sein de la hiérarchie NC impliquerait.$\textrm{P}/\textrm{poly}$$\textrm{P}=\textrm{BPP}$$\textrm{NC}$

La classe uniforme-RNC a été beaucoup étudiée. C'est un problème ouvert de savoir si uniforme-RNC = uniforme-NC. Uniform- (R) NC correspond à des PRAM (randomisées) avec de nombreux processeurs polynomiaux et un temps d'exécution polylogarithmique (voir le Handbook of Theoretical Computer Science Vol. A). La question est donc de savoir si chaque algorihm parallèle randomisé efficace peut être dérandomisé.

Étant donné que les tests d'identité des déterminants symboliques sont en RNC uniforme, la dérandomisation des RNC implique des limites inférieures de circuit par les résultats de Kabanets & Impagliazzo (Computational Complexity, 13 (1-2), pages 1-46, 2004).

Un cas particulier important est la question de savoir si nous pouvons calculer des correspondances parfaites en uniforme-NC. Il existe plusieurs algorithmes parallèles randomisés connus, mais nous ne savons pas s'il existe un algorithme déterministe. Récemment, Fenner, Gurjar et Thierauf (STOC 2016) ont montré que nous pouvons calculer des appariements parfaits dans des graphiques bipartites par des circuits uniformes de profondeur polylogarithmique et de taille quasipolynomiale.