Classes de complexité de l'aléatoire et des petits circuits

Que soit une classe de complexité et BP- C la contrepartie aléatoire de C définie comme BPP par rapport à P . Plus formellement, nous fournissons un nombre aléatoire de bits polynomial 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}$

On sait que pour la classe des circuits non uniformes on a :$\textrm{BPAC}^0=\textrm{AC}^0$

Miklós Ajtai, Michael Ben-Or: un théorème sur les calculs probabilistes à profondeur constante STOC 1984: 471-474

Les généralisations de ce théorème sont-elles connues? Par exemple, savons-nous si (toujours dans le cadre non uniforme)? Cette dernière question me semble en quelque sorte non triviale car il semble plausible que par exemple s , t -Connectivité soit dans BPNC 1 .$\mathrm{BPNC}^1=\mathrm{NC}^1$$s,t\textrm{-Connectivity}$$\textrm{BPNC}^1$

Un article pertinent sur le sujet: /mathpro/35184/use-of-randomness-in-constant-parallel-time

$\mathrm{NC^1}$$\mathrm{BP}$$\mathrm{BPP\subseteq P/poly}$$2^{-n}$$O(n)$ $2^n$$n$simultanément avec une probabilité non nulle, et en particulier, il existe une telle séquence. Nous pouvons le câbler dans le circuit.

$O(n)$$\mathrm{TC^0}$$\mathrm{TC^0}$

$\mathrm{AC^0}$