Aleatoriedad y clases de complejidad de circuitos pequeños.

Deje ser una clase de la complejidad y BP- C sea el homólogo aleatorio de C definida como BPP con respecto a P . Más formalmente, proporcionamos polinómicamente muchos bits aleatorios y aceptamos una entrada si la probabilidad de aceptar es superior a $\mathcal{C}$$\textrm{BP-}\mathcal{C}$$\mathcal{C}$$\textrm{BPP}$$\textrm{P}$ .$\frac{2}{3}$

Se sabe que para la clase de circuitos no uniformes tenemos :$\textrm{BPAC}^0=\textrm{AC}^0$

Miklós Ajtai, Michael Ben-Or: un teorema sobre cálculos probabilísticos de profundidad constante STOC 1984: 471-474

¿Se conocen las generalizaciones de este teorema? Por ejemplo, ¿sabemos si (todavía en la configuración no uniforme)? Esta última pregunta me parece de alguna manera no trivial ya que parece plausible que, por ejemplo , s , t -Connectivity esté en BPNC 1 .$\mathrm{BPNC}^1=\mathrm{NC}^1$$s,t\textrm{-Connectivity}$$\textrm{BPNC}^1$

Una publicación relevante sobre el tema: /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$simultáneamente con probabilidad distinta de cero, y en particular, existe tal secuencia. Podemos conectarlo al circuito.

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

$\mathrm{AC^0}$