Eine Charakterisierung mit fester Tiefe von ? ?

Dies ist eine Frage zur Schaltungskomplexität. (Definitionen finden Sie unten.)

Yao und Beigel-Tarui zeigten, dass jede Schaltkreisfamilie der Größe eine äquivalente Schaltkreisfamilie der Größe der Tiefe zwei aufweist , wobei das Ausgangsgatter eine symmetrische Funktion ist und die zweite Ebene besteht von Gattern von fan-in. Dies ist ein ziemlich bemerkenswerter "Tiefenzusammenbruch" einer Schaltkreisfamilie: Ab einem Schaltkreis mit einer Tiefe von 100 kann die Tiefe auf 2 verringert werden, mit nur einer quasi-polynomiellen Explosion (und einem ausgefallenen, aber immer noch eingeschränkten Gate oben).$ACC^0$$s$$s^{poly(\log s)}$$AND$$poly(\log s)$

Meine Frage: Gibt es eine bekannte Möglichkeit, eine Schaltkreisfamilie auf ähnliche Weise auszudrücken ? Ehrgeiziger, was ist mit einer Schaltkreisfamilie? Mögliche Antworten hätten die Form: "Jede Schaltung der Größe kann durch eine Familie mit zwei Tiefen der Größe erkannt werden , wobei das Ausgangsgatter eine Funktion des Typs und die zweite Ebene von Gattern den Typ hat " .$TC^0$$NC^1$$TC^0$$s$$f(s)$$X$$Y$

Es muss nicht hat sein Tiefen zwei, jede Art von Fest Tiefes Ergebnis wäre interessant. Es wäre sehr interessant zu beweisen, dass jede Schaltung in der Tiefe 3 durch eine Schaltung dargestellt werden kann, die nur aus symmetrischen Funktionsgattern besteht.$TC^0$

Einige kleinere Beobachtungen:

1. Wenn die Antwort für jede Boolesche Funktion trivial (wir können jede Funktion als von ausdrücken ). Nehmen wir zur Konkretisierung an, dass .$f(n)=2^n$$OR$$2^n$ $AND$$f(n) = 2^{n^{o(1)}}$

2. Die Antwort ist auch trivial, wenn entweder oder eine beliebige in berechenbare Funktion sein darf ... :) Ich bin offensichtlich an "einfacheren" Funktionen interessiert, was auch immer dies bedeutet. Es ist etwas rutschig zu definieren, da es symmetrische Funktionsfamilien gibt, die nicht berechenbar sind. (Es gibt unäre Sprachen, die nicht kompatibel sind.) Wenn Sie möchten, können Sie einfach und durch symmetrische Funktionen in der Anweisung ersetzen. Ich würde mich jedoch für jede andere gute Auswahl an Toren interessieren.$X$$Y$$TC^0$$X$$Y$

(Nun einige kurze Erinnerungen an die Notation:

$ACC^0$ ist die Klasse, die von einer Familie unbegrenzter Fan-In-Schaltungen mit konstanter Tiefe mit , und Gattern für eine von der Schaltungsgröße unabhängige Konstante . Ein Gatter gibt wenn die Summe seiner Eingänge durch teilbar ist .$AND$$OR$$MOD_m$$m > 1$$MOD_m$$1$$m$

$TC^0$ ist die Klasse, die von Schaltkreisen mit konstanter Tiefe und Gates mit unbegrenztem Fan-In erkannt wird .$MAJORITY$

$NC^1$ ist die Klasse, die von Schaltungen mit logarithmischer Tiefe mit , , Gattern mit begrenztem Fan-In erkannt wird .$AND$$OR$$NOT$

Es ist bekannt, dass wenn die Schaltungsgröße in der Anzahl der Eingänge auf ein Polynom beschränkt ist.)$ACC^0 \subseteq TC^0 \subseteq NC^1$

Hier ist eine leichte Erweiterung meines Kommentars zur Antwort von Boaz. Agrawal, Allender und Datta geben in ihrem Aufsatz On , und Arithmetic Circuits A C $TC^0$$AC^0$ eine Charakterisierung von in Bezug auf arithmetische Schaltungen. Sie zeigen nämlich, dass eine Sprache in wenn und nur es eine Funktion in und eine ganze Zahl so dass A T C 0 f ≤ A C 0$TC^0$$A$$TC^0$$f$$\sharp AC^0$$k$

f ( x ) = 2 | x | $x \in A$ genau dann, wenn .$f(x) = 2^{|x|^k}$

Beachten Sie, dass eine spezielle Form einer Konstanttiefen-Arithmetikschaltung über (nur die Konstanten 0 und 1 sind zulässig, und variable Eingaben können oder ). Z x i 1 - x $\sharp AC^0$$Z$$x_i$$1-x_i$

Angesichts der Tatsache, dass es, wie Boaz in seiner Antwort ausführt, eine nicht triviale Tiefenreduktion für arithmetische Schaltungen gibt, könnte dies ein Grund zur Prüfung sein.

Der Satz von Barrington sollte für Poly-Size-Schaltkreise der Tiefe 3 mit einem nicht allzu seltsamen oberen Gate liefern (multipliziert 5 Zyklen).$NC^1$

Ich kenne keine Antwort und schätze, es ist eine offene Frage. Es gibt nur sehr wenige bekannte Beispiele für solche "überraschenden Simulationen", die Yao / Beigel-Tarui und Barrington ähneln. Eine Sache in dieser Richtung, die in den Sinn kommt, ist das Ergebnis von Valiant, dass für jedes , das durch -tiefe berechnet werden kann. -große Schaltung, es gibt in , das mit auf Eingängen übereinstimmt . (Und wenn die Schaltung für nur lineare Operationen verwendet, führt die Schaltung für zur unteren Grenze / Matrixsteifigkeitsverbindung). Aber anders als$f:{0,1}^n\rightarrow{0,1}^n$$O(\log n)$$O(n)$$g$$NC_0[n^{\epsilon}]$$f$$2^{n-o(n)}$$f$$g$$NC^1$Hierbei handelt es sich um Funktionen mit mehreren Ausgängen und auch nur für Schaltungen mit linearer Größe. Es ist auch zu beachten, dass für arithmetische Schaltungen eine nicht triviale Reduktion auf die Tiefe 4 bekannt ist.