Die effizienteste Möglichkeit, eine Schaltung in eine Schaltung (beliebiger Tiefe) mit Gate-Fanout 1 zu konvertieren

BEARBEITEN (22. August 2011):

Ich vereinfache die Frage weiter und lege ein Kopfgeld auf die Frage. Vielleicht hat diese einfachere Frage eine einfache Antwort. Ich werde auch alle Teile der ursprünglichen Frage durchstreichen, die nicht mehr relevant sind. (Vielen Dank an Stasys Jukna und Ryan O'Donnell für die teilweise Beantwortung der ursprünglichen Frage!)

Hintergrund:

Bei einer AC ⁰ -Schaltung mit der Tiefe k und der Größe S gibt es eine weitere AC ⁰ -Schaltung, die dieselbe Funktion mit der Tiefe k und der Größe berechnet, so dass die neue Schaltung für alle Gatter Fanout = 1 hat. Mit anderen Worten, die Schaltung sieht wie ein Baum aus (außer an den Eingängen, da die Eingänge auf mehr als ein Gate auffächern können). Eine Möglichkeit, dies zu tun, besteht darin, alle Gates mit Fanout> 1 zu duplizieren, bis alle Gates Fanout = 1 haben.$O(S^k)$

Aber ist dies die effizienteste Methode, um AC ^0- Stromkreise in AC ^0- Stromkreise mit Fanout 1 umzuwandeln? In Vorlesung 14 der Kursnotizen von Ryan O'Donnell habe ich Folgendes gelesen :

Bedeutet dies, dass es eine Möglichkeit gibt, einen Schaltkreis mit einer Tiefe von k AC ⁰ der Größe S in einen Schaltkreis mit AC ⁰ mit Fanout 1, Tiefe k und Größe ? Wenn ja, wie wird das gemacht und ist dies die bekannteste Methode? $(2kS)^2$

Ursprüngliche Frage:

Was ist bei einer AC ⁰ -Schaltung mit der Tiefe k und der Größe S die bekannteste Methode (in Bezug auf die Minimierung der Schaltungsgröße der resultierenden Schaltung), um diese in eine AC ⁰ -Schaltung mit der Tiefe k und dem Gate-Fanout 1 umzuwandeln? Gibt es dafür bekannte Untergrenzen?

Neuere, einfachere Frage:

Diese Frage ist eine Entspannung der ursprünglichen, bei der ich nicht darauf bestehe, dass die resultierende Schaltung eine konstante Tiefe aufweist. Wie oben erläutert, gibt es eine Möglichkeit, eine AC ⁰ -Schaltung mit der Tiefe k, Größe S, in eine Schaltung mit der Größe umzuwandeln, so dass die neue Schaltung für alle Gatter Fanout = 1 aufweist. Gibt es eine bessere Konstruktion?$O(S^k)$

Was ist bei einer AC ⁰ -Schaltung mit der Tiefe k und der Größe S die bekannteste Methode (in Bezug auf die Minimierung der Schaltungsgröße der resultierenden Schaltung), um diese in eine Schaltung beliebiger Tiefe mit Gate-Fanout 1 umzuwandeln?

Ich werde versuchen, meine bisherigen Kommentare zusammenzufassen.

Lassen Sie uns zunächst die Tatsache ignorieren, dass Ihre ursprüngliche Schaltung die (konstante) Tiefe . Nehmen Sie einfach an, dass es Größe . Sei die kleinste Zahl, so dass jede unbegrenzte Fanin-Schaltkreisgröße in eine unbegrenzte Fanin-Formel der Größe transformiert werden kann . Ich behaupte, das Beste, was wir bisher tun können, ist . Es ist sogar nicht bekannt, ob eine (Fanin-2) -Schaltung der Größe durch eine Formel mit einer Größe kleiner als simuliert werden kann .S A S F O ( S A ) A = O ( S / log 2 S ) , S = O ( n ) exp ( n / log n $k$$S$$A$$S$$F$$O(S^A)$$A=O(S/\log^2 S)$$S=O(n)$$\exp(n/\log n)$

Um die Behauptung zu zeigen, transformieren wir die Formel in eine Fanin-2-Formel der Größe . Es ist bekannt, dass die Tiefe jeder Formel in ihrer Größe logarithmisch gemacht werden kann, dh . [Dies wurde zuerst von Khrapchenko 1968 gezeigt, und dann wurde die Konstante unter big-O von mehreren Autoren auf verbessert .] Andererseits das bekannteste Ergebnis für Fanin-2-Schaltungen [Paterson und Valiant, TCS 2 (3), 397-400] besagt, dass . Somit ist eine Simulation mit viel kleiner alsF ' M = O ( S 2 A ) D F ' D = O ( log M ) = O ( A log S ) D ≤ 1,73 log 2 M D e p t h = O ( S i z e / log S i z e ) A S / log 2$F$$F′$$M=O(S^{2A})$$D$$F′$$D=O(\log M)=O(A\log S)$$D\leq 1.73\log_2M$$Depth=O(Size/\log Size)$$A$$S/\log^2 S$ würde die bekannteste Größentiefensimulation für Schaltungen verbessern.

Dies ist jedoch nur ein "Wort der Vorsicht" - es beantwortet Ihre Frage nicht, da Sie annehmen, dass Ihre ursprüngliche Schaltung eine konstante Tiefe , was impliziert, dass wir in diesem Fall einfach (oder wenn wir ein einzelnes Ausgangstor haben). Die Stärke der Paterson-Valiant-Simulation besteht darin, dass sie für beliebige, sogar sehr unsymmetrische Schaltungen gilt, deren Tiefe fast die gesamte Größe beträgt! Aber in Ihrer Einstellung für die beschränkte Tiefe ist auch der Fall nicht klar: Kann jeder Tiefen-3-Kreis der Größe in eine Tiefen-3-Formel der Größe viel kleiner als transformiert werdenA = k A = k - 1 k = 3 S S $k$$A=k$$A=k−1$$k=3$$S$$S^2$? Ich denke, die Antwort sollte "nein" sein (könnte eine interessante Übung für Studenten sein). Eine Formel der Tiefe 3 ist nur ein großer OR von CNFs. Die Frage ist, ein OR von CNFs zu finden, die viele Klauseln gemeinsam haben, ansonsten aber "sehr unterschiedlich" sind, um eine große Tiefe-3-Formel zu erzwingen.

Das Problem ist, dass wir eine Formel erhalten möchten (eine Fanout-1-Schaltung). Wie bereits erwähnt, vereinfacht das Zulassen von Gates für Fanin-2 die Simulation: Hoover, Klawe und Pippenger [JACM 31 (1), 1980] zeigen, dass jeder Fanin-2-Schaltkreis der Größe und Tiefe ein äquivalentes Fanin-2 und Fanout aufweist -2 Schaltung der Größe und Tiefe . Wenn also Fanin nicht begrenzt ist, hat die resultierende Schaltung die Größe und die Tiefe .D 3 S - 2 n 2 D O ( S 2 ) O ( D log S $S$$D$$3S−2n$$2D$$O(S^2)$$O(D\log S)$

Es gibt noch ein anderes Ergebnis, das irgendwie mit Ihrer Frage zusammenhängt. Lozhkin (1981) hat bewiesen, dass, wenn eine Boolesche Funktion durch eine Formel der Tiefe und der Größe berechnet werden kann , durch eine Fanin-2-Formel der Tiefe (dies folgt aus Satz 6.2 in meinem Buch). Beachten Sie, dass eine triviale Obergrenze nur (wenn wir jedes einzelne Tor durch einen Baum der Tiefe simulieren würden ).A C 0 k S f D ≤ k - 1 + ⌈ log 2 S ⌉ D ≤ k log S log $f$$AC^0$ $k$$S$$f$$D\leq k-1+\lceil\log_2S\rceil$$D\leq k\log S$$\log S$