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

10

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 2 liegtCBP-CCBPPP .23

Es ist bekannt, dass für ungleichmäßige Schaltungsklassen :BPAC0=AC0

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 .BPNC1=NC1BPNC 1s,t-ConnectivityBPNC1

Ein relevanter Beitrag zu diesem Thema: /mathpro/35184/use-of-randomness-in-constant-parallel-time

CP
quelle
2
Was treibt Ihre Vermutung zur Konnektivität an?
Michaël Cadilhac
4
NC1
8
TC0NC1AC0
1
TC0BPC=C
1
@ EmilJeřábek: Ah, ich verstehe. Ich denke, es ist grenzwertig; Es ist offensichtlich keine Forschungsfrage , aber sie wurde eindeutig ernsthaft von jemandem mit etwas Forschungserfahrung in Komplexität gestellt, der einfach irregeführt wurde, indem er versuchte, Ajtai-Ben-Or zu erweitern, anstatt den einfacheren Ansatz zu verwenden.
Joshua Grochow

Antworten:

10

NC1BPBPPP/poly2nO(n) 2nngleichzeitig mit einer Wahrscheinlichkeit ungleich Null, und insbesondere existiert eine solche Sequenz. Wir können es fest in die Schaltung verdrahten.

O(n)TC0TC0

AC0

Emil Jeřábek
quelle