Komplexitätsklassen für Zufälligkeit und kleine Schaltkreise

Lassen eine Komplexitätsklasse und BP- C die randomisierten Pendant sein C definiert BPP mit Bezug auf P . Formal stellen wir polynomiell viele Zufallsbits bereit und akzeptieren eine Eingabe, wenn die Wahrscheinlichkeit zu akzeptieren über $\mathcal{C}$$\textrm{BP-}\mathcal{C}$$\mathcal{C}$$\textrm{BPP}$$\textrm{P}$ .$\frac{2}{3}$

Es ist bekannt, dass für ungleichmäßige Schaltungsklassen :$\textrm{BPAC}^0=\textrm{AC}^0$

Miklós Ajtai, Michael Ben-Or: Ein Satz über probabilistische Berechnungen konstanter Tiefe STOC 1984: 471-474

Sind Verallgemeinerungen dieses Satzes bekannt? Wissen wir zum Beispiel, ob (immer noch in der ungleichmäßigen Einstellung)? Diese letzte Frage erscheint mir irgendwie nicht trivial, da es plausibel erscheint, dass sich beispielsweise in .$\mathrm{BPNC}^1=\mathrm{NC}^1$BPNC$s,t\textrm{-Connectivity}$$\textrm{BPNC}^1$

Ein relevanter Beitrag zu diesem Thema: /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$gleichzeitig mit einer Wahrscheinlichkeit ungleich Null, und insbesondere existiert eine solche Sequenz. Wir können es fest in die Schaltung verdrahten.

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

$\mathrm{AC^0}$