Minimale Baumbreite der Schaltung für MAJORITY

Was ist die minimale Baumbreite einer Schaltung über $\{\wedge,\vee,\neg\}$ für die Berechnung von MAJ?

Hier MAJ $:\{0,1\}^n \rightarrow \{0,1\}$ gibt 1 aus, wenn mindestens die Hälfte seiner Eingänge $1$ .

Ich kümmere mich nur um die Größe der Schaltung (sollte polynomisch sein) und dass ein Eingang nur einmal gelesen werden sollte, obwohl das Fan-Out eines Eingangsgatters beliebig sein kann (dies wirkt sich entscheidend auf die Baumbreite der Schaltung aus - die Verzweigung Programme, die aus Barringtons Theorem aus dem MAJ $\in$ $\mathsf{NC}^1$ wurden und als Versatzschaltungen interpretiert werden, helfen nicht). Und natürlich ist die Baumbreite das Entscheidende. Ich nicht kümmere sich um die Tiefe oder andere Parameter.

Einige der gängigen Schaltkreise für MAJ umfassen:

• Wallace-Baum-Schaltkreise (z. B. Satz 8.9 hier ), die den 3-zu-2-Trick verwenden, um MAJ in $\mathsf{NC}^1$ ?
• Valiants monotone $\mathsf{NC}^1$ -Schaltungen für MAJ (zB Satz 4 hier )
• $\log^{O(1)}{n}$ Tiefensortierungsnetzwerk wieBatcher-Sortierung
• AKS- Sortiernetzwerk

Hat einer von ihnen eine begrenzte oder sogar polylogarithmische Baumbreite?

Oder in der Tat,

Gibt es Gründe zu der Annahme, dass es für MAJ keine begrenzten Baumbreitenschaltungen gibt?

Beachten Sie, dass jede Funktion, die von einer Schaltung mit begrenzter Baumbreite berechnet wird, von einer -Schaltung berechnet werden kann, selbst wenn keine einmalige Lesebestimmung über JansenSarma erfolgt . Somit würde die Unplausibilität einer solchen Schaltungsfamilie anzeigen, dass diese Grenze im Fall von einmal gelesenen Schaltungen weiter verschärft werden kann.$\mathsf{NC}^1$

Beantwortung der Hälfte von Samirs Frage.

Let werden , um eine DAG und V 1 , V 2 ⊆ V zwei Untergruppen von Scheitelpunkten sein G . Wir bezeichnen mit E ( V 1 , V 2 ) die Menge aller Kanten in G mit einem Endpunkt in V 1 und einem anderen Endpunkt in V 2 . Wenn ω = ( v 1 , . . . , V n$G=(V,E)$$V_1,V_2\subseteq V$$G$$E(V_1,V_2)$$G$$V_1$$V_2$$\omega = (v_1,...,v_n)$$G$ ω G o w ( G ) = min

Wir behaupten, dass die MEHRHEIT von Bits in der Online-Breite und daher in der Baumbreite berechnet werden kann . Die Schaltung simuliert eine Online - Algorithmus, der eine Eingangs - Bit liest zu einem Zeitpunkt und fügt zu einem Zähler mit Bits , wenn und nur wenn . Zu Beginn wird der Zähler auf initialisiertO ( log N ) O ( log N ) b b O ( log N ) b = 1 0 C = ( A D D 1 , A D D 2 , . . . , A D D n , C O M P ) A D D i A D D i + 1 A $n$$O(\log n)$$O(\log n)$$b$$b$$O(\log n)$$b=1$$0$. Am Ende akzeptiert die Schaltung genau dann, wenn der Wert des Zählers größer als n / 2 ist. Es ist leicht zu erkennen, dass die Gatter einer Schaltung ADD, die eine zum Zählerregister hinzufügt, topologisch so angeordnet werden können, dass sie eine konstante Online-Breite haben, da diese Schaltungen nur eine Weiterführungsoperation implementieren müssen. Die Gesamtschaltung ist eine Folge von Schaltungen wobei der Ausgang von mit dem Eingang von und der Ausgang von mit dem verbunden ist Eingabe von COMP. Wenn wir nun die Gesamtschaltung topologisch so ordnen , dass alle Gates von vor den Gates von und allen Gates von erscheinen$C=(ADD_1,ADD_2,...,ADD_n,COMP)$$ADD_i$$ADD_{i+1}$ C A D D i A D D i + 1 A D D n O ( log n $ADD_n$$C$$ADD_i$$ADD_{i+1}$$ADD_n$ erscheint vor den Toren von COMP, dann hat diese topologische Reihenfolge die Online-Breite . Diese Konstruktion ist in Abbildung 1 eines meiner Arbeiten dargestellt, um zu zeigen, dass die Wahrscheinlichkeitsverstärkung in logarithmischer Online-Breite erfolgen kann.$O(\log n)$

Obs: Die Tiefe der Schaltung C ist .$O(n)$

Beantwortung der anderen Hälfte der Frage - hier ist eine Beweisskizze für eine Untergrenze für die Baumbreite für eine Konstante . Die Grenze ist unabhängig von der Größe oder einem anderen Aspekt der Schaltung. Im Rest des Arguments ist die Schaltung, ist die Baumbreite von und ist die Anzahl der Eingangsgatter.c C t C $c \cdot \log n$$c$$C$$t$$C$$n$

Der erste Schritt besteht darin, das ausgeglichene Trennzeichen-Lemma für Diagramme mit begrenzter Baumbreite zu verwenden . Die Gatter (einschließlich der Eingangsgatter) der Schaltung können in drei Teile , und , so dass und sowohl als auch enthalten mindestensEingangs - Gates, und es gibt keine Lichtbögen (Drähte) zwischen und .$L$$R$$S$$|S| \leq t+1$$L$$R$$n/3-|S|$$L$$R$

Im Rest des Beweises ist die einzige Eigenschaft der Schaltung, die wir verwenden werden, diese Aufteilung - der Beweis gibt also tatsächlich eine Untergrenze für die Größe eines ausgeglichenen Separators wie oben.$S$

Wenn wir zur Hand haben, konstruieren wir eine Schaltung aus wie folgt: Für jedes Gate in machen zwei weitere Gates und und lassen und in . Sie alle Drähte, die von nach stattdessen in . Für alle Drähte, die von nach , gehen stattdessen zu . Sei $(L,S,R)$$C'$$C$$g$$S$$g_L$$g_R$$g_L$$g_R$$g$$g$$L$$g_L$$g$$R$$g_R$

Für jede der Zuordnungen zu eine Schaltung erstellt, die 1 ausgibt, wenn (a) die Zuordnung zu den Eingangsgattern die Ausgabe von wahr macht und (b) die Zuordnung zu den Eingangsgattern alle setzt Tore von wie vermutet. Nennen Sie diese Schaltungen , , für . Es ist zu beachten, dass die Schaltung natürlich in zwei Teilschaltungen und zerfällt, so dass nur von den Eingangsgattern von abhängt , nur von den Eingangsgattern von$2^{|S'|}$$S'$$C'$$S'$$C_1$$C_2$$C_3 \ldots C_x$$x \leq 8^t$$C_i$$C_i^L$$C_i^R$$C_i^L$$L \cup S'$$C_i^R$$R \cup S'$ , und für jede mögliche Zuordnung zu dem Eingang - Gates haben wir , dass .$C_i = C_i^L \wedge C_i^R$

Da jede Zuordnung zu den Eingangsgattern mit einer Vermutung für das, was in passiert, übereinstimmt wir, dass . Daher haben wir die Schaltung als ODER (von Fanin ) von UNDs (von Fanin ) umgeschrieben, wobei der UND- Gatternummer der Ausgang von bzw. zugeführt wird .$S'$$C' = C_1 \vee C_2 \vee C_3 \ldots \vee C_x$$C$$8^t$$2$$i$$C_i^L$$C_i^R$

Sei die Menge der obersten UND-Gatter. Wir werden zuerst beweisen, dass. Dies ergibt eine einfache Untergrenze für . Wir werden uns dann als besser gebunden erweisen.$Z$$2^{|Z|} \geq n/3-|S|$$\log \log n$$t$

Angenommen,und nehme an, dass weniger Eingangsgatter als . Dann enthalten sowohl als auch mindestensEingangsgatter. Nach dem Pigeon-Hole-Prinzip gibt es zwei verschiedene Zahlen und so dass es zwei verschiedene Zuordnungen zu den Eingangsgattern von , eine, die Gatter auf wahr setzt, eine, die setzt , so dass die Schaltungen , alle dasselbe aus. Es gibt jedoch eine Zuordnung zu den Eingangsgattern in$2^{|Z|} < n/3-|S|$$L$$R$$L$$R$$n/3-|S|$$i$$j$$L$$i$$j$$C_1^L$$C_2^L \ldots C_x^L$$R$so dass MAJORITY FALSE ausgibt, wenn Gates in auf true gesetzt sind, und MAJORITY TRUE ausgibt, wenn Gates in auf true gesetzt sind. Dies ist ein Widerspruch und somit Dies bedeutet, dass die Baumbreite mindestens .$i$$L$$j$$L$$2^{|Z|} \geq n/3-|S|$$\log \log n$

Wir zeigen jetzt eine bessere Grenze:. Angenommen, wlog, dass weniger Eingangsgatter als . Dann enthalten sowohl L als auch R mindestensEingangsgatter. Betrachten Sie die „alle falsch“ Zuordnung zu . Sei die kleinste Anzahl von Eingangsgattern von , die auf true gesetzt werden müssen, so dass MAJ TRUE ausgibt, vorausgesetzt, dass alles von auf false gesetzt ist.$|Z| \geq n/3-|S|$$L$$R$$n/3-|S|$$L$$r$$R$$L$

Da das Setzen von auf alle falschen und genau Eingangsgatter von auf wahr die MAJORITY-Ausgabe ergibt, muss es einige so dass TRUE ausgibt, wlog dies . Alle Zuweisungen an mit weniger als true Eingangsgattern müssen auf false setzen. Da das Setzen von Eingangsgatter von auf true und von Eingangsgattern von auf true den MAJORITY-Ausgang ergibt , muss das Setzen von Gate von auf true mindestens eins ergebenr R 1 i C L i C L 1 R r C R 1 1 L r - 1 R 1 1 L C L i i ≠ 1 i = 2 R r - 2 C R 2 r $L$$r$$R$$1$$i$$C_i^L$$C_1^L$$R$$r$$C_1^R$$1$$L$$r-1$$R$$1$$1$$L$$C_i^L$ outpur true für . wlog wir können annehmen . Dann müssen alle Zuweisungen an , die höchstens Eingangsgatter auf true setzen, auf false setzen, und so weiter - wir können dieses Argument mal wiederholen . Dies bedeutet aber, dassGeben Sie eine Untergrenze für .$i \neq 1$$i=2$$R$$r-2$$C_2^R$$r$c ⋅ log n $|Z| \geq r \geq n/3-|S|$$c \cdot \log n$$t$

[Mir ist bewusst, dass diese Skizze an manchen Stellen etwas handgewellt wird. Fragen Sie weg, ob etwas unklar ist ...]