2.5 Majority

Unser Ziel in diesem Teilkapitel ist es, Schaltkreise für die Majority-Funktion zu bauen:

Diese nimmt

n

Bits als Input und gibt 1 aus, wenn mehr als

n / 2

davon 1 sind. Für

n = 3

heißt dass, das mindestens zwei Input-Bits 1 sein müssen. Als Formel kann man das so schreiben:

{Maj}_{3} (x, y, z) = (x \land y) \lor (x \land z) \lor (y \land z)

und als Schaltkreis so:

Wie können wir das sinnvoll verallgemeinern für größere $n$ ? Was geschieht, wenn wir einfach die Wahrheitstabellen-Methode anwenden? Falls $n$ ungerade ist, dann sieht man leicht, dass die Wahrheitstabelle in genau $2^{n - 1}$ vielen Zeilen eine 1 stehen hat und in ebenso vielen eine 0.

Übungsaufgabe 2.5.1 Sei

n

eine ungerade Zahl. Zeigen Sie, dass

{Maj}_{n}

für genau die Hälfte aller

2^{n}

möglichen Eingaben eine 1 ausgibt (und für die andere Hälfte eine 0).

Wir erhielten also eine DNF mit $2^{n - 1}$ vielen AND-Gates. Das ist sehr groß, gemessen daran, dass Zählen und mit $n / 2$ vergleichen ja nicht besonders schwierig klingt. Hier ist eine kleine Verbesserung, demonstriert am Beispiel $n = 7$ . Wenn wir für $n = 7$ mit Hilfe einer Wahrheitstabelle eine DNF konstruieren, erhalten wir ja unter Anderem den Term $T := x_{1} {\bar{x}}_{2} x_{3} x_{4} {\bar{x}}_{5} x_{6} x_{7},$ da der Input ${Maj}_{7} (1011011) = 1$ ist. Schauen wir uns nun den Term $T^{'}$ an, den wir erhalten, wenn wir alle negativen Literale aus $T$ löschen: $T^{'} := x_{1} x_{3} x_{4} x_{6} x_{7} .$ Wenn dieser Term 1 wird, dann sind $x_{1} = x_{3} = x_{4} = x_{6} = x_{7}$ sein, also insgesamt fünf Input-Bits 1, und ${Maj}_{7}$ gibt 1 aus. Hier ist also eine Vereinfachung: wir folgen der Wahrheitstabellen-Methode, lassen aber alle negativen Literale weg. Das Ergebnis ist etwas kleiner und immer noch korrekt. Schauen Sie sich nun den Term $x_{1} {\bar{x}}_{2} {\bar{x}}_{3} x_{4} {\bar{x}}_{5} x_{6} x_{7}$ an. Auch dieser kommt in der Wahrheitstabelle vor, da ${Maj}_{7} (1001011) = 1$ gilt. In unserer neuen Konstruktion wird dieser zu $x_{1} x_{4} x_{6} x_{7}$ vereinfacht. Nun schauen Sie: wenn $T^{'}$ den Wert 1 ausgibt, dann gibt $x_{1} x_{4} x_{6} x_{7}$ auf jeden Fall 1 aus, und ${Maj}_{7}$ wird 1; $T^{'}$ ist also redundant. Irgendwie ist das ja auch klar: zu verlangen, dass die fünf Variablen $x_{1}, x_{3}, x_{4} x_{6}, x_{7}$ alle mit 1 abstimmen, ist zwar hinreichend, aber eben schon mehr als nötig. Es reicht also, sich auf alle Terme mit genau 4 Variablen zu beschränken. Im allgemeinen sei $k = ⌈ \frac{k + 1}{2} ⌉$ . Dann gilt

\begin{array}{r} (1) & {Maj}_{n} (x_{1}, \dots, x_{n}) = \underset{\begin{array}{c} I \subseteq [n] \\ | I | = k \end{array}}{⋁} \underset{i \in I}{⋀} x_{i} . \end{array}

Diese Konstruktion hat nun $(\binom{n}{k})$ Terme, von denen jeder aus $k$ Variablen besteht. Ist das nun gut oder schlecht?

Lemma. 2.5.1 Es gilt

(\binom{n}{⌈ n / 2 ⌉}) \geq \frac{2^{n}}{n + 1} .

Beweis. Sei

k \in {1, \dots, n}

. Vergleichen wir

(\binom{n}{k})

mit

(\binom{n}{k - 1})

\begin{aligned} \frac{(\binom{n}{k})}{(\binom{n}{k - 1})} & = \frac{\frac{n!}{k! (n - k)!}}{\frac{n!}{(k - 1)! (n - k + 1)!}} = \frac{n - k + 1}{k} \end{aligned}

und somit

\begin{aligned} (\binom{n}{k}) & \geq (\binom{n}{k - 1}) ⟺ \\ n - k + 1 & \geq k ⟺ \\ 2 k & \leq n + 1 ⟺ \\ k & \leq \frac{n + 1}{2} ⟺ \\ k & \leq ⌊ \frac{n + 1}{2} ⌋ = ⌈ \frac{n}{2} ⌉ . \end{aligned}

Aus der letzten Zeile folgt nun, dass

(\binom{n}{k})

durch

k := ⌈ \frac{n}{2} ⌉

maximiert wird, also

(\binom{n}{k}) \leq (\binom{n}{⌈ \frac{n}{2} ⌉})

gilt.

Als nächstes müssen wir uns die Definition von $(\binom{n}{k})$ ins Gedächtnis rufen. Nein, $\frac{n!}{k! (n - k)!}$ ist nicht die Definition, sondern eine Formel dafür. Die Definition ist: $(\binom{n}{k})$ ist die Menge der Teilmengen von ${1, \dots, n}$ , die Größe $k$ haben. Wieviele Teilmenge (jeglicher Größe) gibt es insgesamt? Genau $2^{n}$ viele: Sie müssen für jede Zahl $i \in {1, \dots, n}$ die Entscheidung treffen, ob $i$ in die Menge soll oder nicht, haben also insgesamt $2^{n}$ Wahlmöglichkeiten. Daher gilt: $\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n} .$ Intuitiv gesprochen heißt das: diese Summe hat $n + 1$ Terme ( $k$ wandert von 0 bis $n$ , also muss der größte Term mindestens ein $(n + 1)$ -tel des Gesamtbetrages sein. Formal: $2^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) \leq \sum_{k = 0}^{n} (\binom{n}{⌈ \frac{n}{2} ⌉}) = (n + 1) \cdot (\binom{n}{⌈ \frac{n}{2} ⌉})$ und somit $(\binom{n}{⌈ \frac{n}{2} ⌉}) \geq \frac{2^{n}}{n + 1},$

wie behauptet.

◻

Unsere neue, bessere Konstruktion benötigt also immer noch mindestens $\frac{2^{n}}{n + 1}$ Terme, was bereits für moderate Werte wie $n = 30$ nicht vertretbar ist.

Majority Top-Down mit `if-then-else`-Gates

Wenden wir nun statt Wahrheitstabelle die Top-Down-Methode an, modifiziert für monotone Funktionen wie in den Lösungen zu den Übungsaufgaben dargestellt. Insbesondere definieren wir Verallgemeinerungen von

{Maj}_{n}

wie folgt:

\begin{aligned} θ_{k}^{n} (x_{1}, \dots, x_{n}) & := {\begin{cases} 1 & falls x_{1} + \dots + x_{n} \geq k \\ 0 & sonst. \end{cases} \end{aligned}

Die Funktion

{Maj}_{n}

ist also ein Speziallfall

θ_{k}^{n}

für

k = ⌈ \frac{n + 1}{2} ⌉

. Wir können

θ_{k}^{n}

rekursiv zerlegen wie folgt:

θ_{k}^{n} (x_{1}, \dots, x_{n}) = (x_{n} \land θ_{k - 1}^{n - 1} (x_{1}, \dots, x_{n - 1})) \lor θ_{k}^{n - 1} (x_{1}, \dots, x_{n - 1})

und somit

θ_{k}^{n}

aus

θ_{k - 1}^{n - 1}

und

θ_{k}^{n - 1}

berechnen. Rekursiv fortgefühtr sieht das dann so aus:

Die Konstruktion endet mit

θ_{0}^{m}

, was immer

1

ausgibt, und mit

θ_{m}^{m}

, was

x_{1} \land \dots \land x_{m}

ist. Die Konstruktion ist leider auch nicht effizient; wenn man mit

C_{k}^{n}

die Anzahl der

θ_{m}^{m}

und

θ_{0}^{m}

in diesem Baum zählt, dann sieht man, dass

\begin{aligned} C_{k}^{n} & = C_{k - 1}^{n - 1} + C_{k}^{n - 1} \\ C_{n}^{n} & = 1 \\ C_{0}^{n} & = 1 \end{aligned}

gilt; sie erfüllt also die gleiche Rekursionsgleichung wie der Binomialkoeffizient

(\binom{n}{k})

, also gilt

C_{k}^{n} = (\binom{n}{k})

. Die Konstruktion ist asymptotisch auch nicht besser als die, aus der Wahrheitstabelle direkt eine monotone DNF zu basteln.

Allerdings können wir die obige Konstruktion offensichtlich effizienter machen, indem wir mehrfach verwendete Zwischenergebnisse wie $θ_{k - 1}^{n - 1}$ nicht doppelt berechnen, also statt dem obigen Baum einen Schaltkreis nach folgendem Pyramidenschema bauen:

Um eine Analogie mit der Programmierpraxis zu bemühen: der Unterschied zwischen den beiden Konstruktionen für $θ_{k}^{n}$ per Baum versus per Pyramidenschema entspricht dem Unterschied zwischen dem rekursiven Code für $(\binom{n}{k})$ ,

def binomial(n,k):
    if k == 0 or k == n:
        return 1 
    else:
        return binomial(n-1,k-1) + binomial(n-1,k)

der exponentielle Laufzeit aufweist, und der effizienten Implementierung mittels Dynamic Programming, bei welchem wir uns die Zwischenergebnisse merken.

Um Größe und Tiefe des Schaltkreises zu analysieren, machen wir eine grobe Abschätzung. Für jedes $θ_{l}^{m}$ , das in unserer Pyramide vorkommt, brauchen wir 2 Gates; $m$ kann die Werte $0, \dots, n$ annehmen und $l$ die Werte $0, \dots, k$ , also bekommen wir insgesamt höchstens $(n + 1) (k + 1)$ graue Kästchen und $O (n^{2})$ Gates. Die Tiefe ist $O (n)$ , da in jedem Schritt von grauem Kasten zu dem nächsttieferen der Wert von $m$ abnimmt. Insgesamt also haben wir gezeigt:

Theorem 2.5.2 Die Funktion

{Maj}_{n} (x_{1}, \dots, x_{n})

kann mit einem Schaltkreis der Größe

O (n^{2})

, Tiefe

O (n)

und Fan-in 2 berechnet werden.

Majority durch Zählen

{Maj}_{n} (x_{1}, \dots, x_{n})

zu bestimmen sollte doch einfach sein: wir zählen die Anzahl der 1en und vergleichen sie mit

⌈ n ⌉ 2

. Wie aber sollen wir zählen? Ganz einfach: mit einem Binäraddierer! Sei

d = ⌈ \log_{2} (n + 1) ⌉

die Anzahl der Bits in der Binärdarstellung von

n

. Wir interpretieren jede Input-Variable

x_{i}

als

d

-stellige Binärzahl, wobei

x_{i} = 1

der Zahl

000 \dots 001

, also 1 entspricht, und

x_{i} = 0

der Zahl

000 \dots 0

, also 0, und addieren die dann auf:

Übungsaufgabe 2.5.2 Bestimmen Sie asymptotisch die Größe und die Tiefe dieses Schaltkreises. Achten Sie besonders bei der Berechnung der Größe darauf, dass die untersten Add-Gadgets ja 1-stellige oder dann 2-stellige Zahlen addieren müssen und erst die weniger obersten Gadgets Zahlen mit

Θ (\log n)

Bits als Input bekommen.

$O (\log n)$ Tiefe mit 2-for-3-Addierern.

Die vorherige Konstruktion mit den Addierern war schon deutlich effizienter als unsere pyramidenartige

θ_{l}^{m}

-Konstruktion, allerdings wurde das Ziel, eine Tiefe von

O (\log n)

zu erreichen, wieder verfehlt, wenn auch knapp. Die Idee, die eine Tiefe von

O (\log n)

erreichen wird, ist ebenso einfach wie genial.

Lemma (2-for-3 Adder) 2.5.3 Es gibt einen Schaltkreis mit

O (n)

Gates, Tiefe 2 und Fan-In 2, der als Input drei

n

-stellige Binärzahlen

x, y, z

nimmt und zwei

n + 1

-stellige Binärzahlen

u, v

ausgibt, so dass

x + y + z = u + v

gilt.

Beweis. Ich demonstriere das Beweisprinzip erst einmal mit drei Zahlen in Basis 10:

Wir addieren also pro Stelle drei (einstellige) Zahlen, führen den Übertrag (das Carry) aber nicht der weiter links stehenden Stelle zu, sondern sammeln alle Überträge und bilden daraus die $n + 1$ -stellige Zahl $u$ . Für Binärzahlen ist das natürlich noch einfacher:

Dieser Schaltkreis hat insgesamt

O (n)

Gates und Tiefe 2 (wobei wir die NOT-Gates im

\oplus

-Gate nicht mitzählen).

◻

Wir interpretieren nun die

n

Inputs

x_{1}, \dots, x_{n}

von Majoroty als einstellige Binärzahlen, sortieren sie in Dreiergruppen und machen per 2-for-3-Addierer daraus

⌈ \frac{2 n}{3} ⌉

Zahlen. Dann machen wir (mit den mittlerweile 2-stelligen Zahlen) weiter und bekommen circa

⌈ \frac{4 n}{9} ⌉

Zahlen. Auf jeder Ebene schrumpft die Anzahl der Zahlen um einen Faktor von

\frac{2}{3}

; nach

\log_{3 / 2} n

Ebenen haben wir schließlich noch zwei mittlerweile (

\log n

)-stellige Zahlen, die wir mit einem "normalen" Binäraddierer addieren. Das Ergebnis vergleichen wir mit dem

\geq

-Schaltkreis mit

\frac{k + 1}{2}

. Was ist die Tiefe des Gesamtschaltkreises? Es ist

\begin{aligned} \log_{3 / 2} n \times depth (2-for-3 adder) \\ + & depth (Binäraddierer für (\log n)-stellige Zahlen) \\ + & depth (\geq -Schaltkreis für (\log n)-stellige Zahlen \\ = & O (\log n) + O (\log \log n) + O (\log \log n) = O (\log n) . \end{aligned}

Die Größe des Schaltkreises wird dominiert von den 2-for-3-Addierern. Wir haben

O (n)

viele davon, allerdings hat jeder bis zu

O (\log n)

viele Gates, da wir ja (

\log n

)-stellige Zahlen addieren müssen; wir haben insgesamt also

O (n \log n)

viele Gates.

Theorem. 2.5.4 Die Konstruktion mit 2-for-3-Addierern gibt uns einen Schaltkreis für Majority mit Fan-in 2, Tiefe

O (\log n)

und Größe

O (n \log n)

Übungsaufgabe 2.5.3 Führen Sie eine genauere Abschätzung der Größe durch. Untersuchen Sie insbesondere:

Wieviele 2-for-3-Addierer haben Sie in Ebene $i$ des Baumes?
Wieviel Bits haben die Zahlen auf Ebene $i$ , und wie groß muss daher der 2-for-3-Addierer sein?
Was ergibt sich insgesamt in Summe?

Wir haben nun also fast alle unserer Ziele erreicht. Allerdings hat die Konstruktion mit 2-for-3-Addierern einen Schönheitsfehler: sie ist nicht monoton. Warum sollten wir das wollen? Nun ja, Majority ist eine monotone Funktion, also ist es ja irgendwie verständlich, dass wir auch einen monotonen Schaltkreis wollen. Unser Pyramidenschema, in dem wir alle $θ_{k}^{m}$ berechnen, ist monoton, hat allerdings leider Tiefe $Ω (n)$ .

Monoton und polylogarithmische Tiefe durch Halbierung und Aufzählung.

Die Idee ist, dass wir, anstatt $θ_{k}^{n}$ aus $x_{n}$ , $θ_{k - 1}^{n - 1}$ und $θ_{k}^{n - 1}$ zu berechnen, versuchen, irgendwie von $n$ auf $n / 2$ runterzukommen. Dann könnten wir rekursiv weitermachen und müssten uns nur durch logarithmisch viele Werte von $n$ wühlen. Wir sehen, dass wir $k$ auf $k + 1$ Weisen als Summe zweier nichtnegativer Zahlen $a + b = k$ schreiben können. Des weiteren zerlegen wir $x \in {0, 1}^{n}$ in $y = (x_{1}, \dots, x_{n / 2})$ und $z = (x_{n / 2 + 1}, \dots, x_{n})$ und sehen, dass $\begin{aligned} \sum_{i} x_{i} & \geq k ⟺ \\ \sum_{i} y_{i} & \geq a \land \sum_{j} z_{j} \geq b für Werte a, b \geq 0 mit a + b = k \end{aligned}$ und somit $\begin{aligned} θ_{k}^{n} (x) & = ⋁_{a = 0}^{k} (θ_{a}^{n / 2} (y) \land θ_{k - a}^{n / 2} (z)) \end{aligned}$ Wenn wir diese Konstruktion rekursiv fortsetzen, erhalten wir $\log n$ Ebenen und somit auf den ersten Blick logarithmische Tiefe. Auf den zweiten Blick erkennen wir, dass wir etwas geschummelt haben: die $⋁$ -Gates haben sehr großen Fan-in, nämlich bis zu $n$ . Um Fan-in 2 zu erreichen, müssen wir jedes $⋁$ -Gate durch einen Binärbaum aus normalen $\lor$ -Gates von Fan-in 2 ersetzen. Dies gibt uns zusätzlich Tiefe $O (\log n)$ pro $⋁$ -Gate; wir erhalten also insgesamt eine Tiefe von $O (\log^{2} n)$ .

Übungsaufgabe 2.5.4 dass polynomiell viele (in diesem Falle:

O (n^{2})

viele) Gates ausreichen. Zeigen Sie, wie die gerade skizzierte Konstruktion so ausgeführt werden kann,

Monoton und logarithmische Tiefe: Valiants probabilitische Konstruktion

Theorem. 2.5.5 Es gibt einen monotonen Schaltkreis mit Fan-in 2, Tiefe

O (\log n)

und Größe

poly (n)

, der

{Maj}_{n}

berechnet.

Beweis. Die Beweismethode, die wir verwenden, ist womöglich neu für Sie. Wir verwenden bei der Konstruktion des Schaltkreises Zufall; am Ende werden wir zeigen, dass dieser zufällige Schaltkreis mit hoher Wahrscheinlichkeit

{Maj}_{n}

auf allen möglichen

2^{n}

Inputs korrekt berechnen, und folgern daraus, das etwas, was mit hoher Wahrscheinlichkeit eintritt, auch existieren muss. Die Existenz folgt also schlussendlich aus einer Wahrscheinlichkeitsrechnung. Das heißt auch, dass ich Ihnen für konkretes

n

, sagen wir

n = 99

, nicht hinschreiben könnte, wie ein korrekter Schaltkreis aussähe; ich könnte die randomisierte Konstruktion durchführen und Ihnen erklären, das der resultierende Schaltkreis höchstwahrscheinlich korrekt ist.

Während des ganzen Beweises müssen Sie sich vor Augen halten, dass wir bei der Konstruktion des Schaltkreises $C$ Zufall verwenden; wir nehmen nicht an, dass die Inputs $x \in {0, 1}^{n}$ in irgendeiner Weise zufällig sind. Wir verwenden also Wahrscheinlichkeitsverteilungen über Schaltkreisen, nicht von über Inputs. Zuerst definieren wir die Signalstärke von Verteilungen über Schaltkreise.

Definition (Signalstärke) 2.5.6 Sei

C

eine Verteilung über Schaltkreise mit Input-Variablen

x_{1}, \dots, x_{n}

. Wir sagen, dass

C

Signalstärke mindestens $δ$ hat, wenn

\forall x \in {0, 1} : \underset{C \in C}{Pr} [C (x) = {Maj}_{n} (x)] \geq \frac{1 + δ}{2}

gilt.

In Worten, wenn der zufällig ausgewählte Schaltkreis $C$ den Wert ${Maj}_{n} (x)$ besser als ein Münzwurf vorhersagt, und zwar um $δ / 2$ besser. Wir können einen ganz einfachen (zufälligen Schaltkreis) bauen, der ein schwache aber positive Signalstärke hat.

Lemma. 2.5.7 Es gibt eine Wahrscheinlichkeitsverteilung

C_{0}

über monotone Schaltkreise der Größe 1, die Signalstärke

\frac{1}{n}

hat. Genauer gesagt gilt für jeden Input

x \in {0, 1}^{n}

: ein nach dieser Verteilung zufällig ausgewählter Schaltkreis

C \sim C_{0}

ist mit Wahrscheinlichkeit mindestens

\frac{1}{2} + \frac{1}{2 n}

korrekt ist. Formal ausgedrückt:

\forall x \in {0, 1}^{n} : \underset{C \sim C_{0}}{Pr} [C (x) = {Maj}_{n} (x)] = \frac{1}{2} + \frac{1}{2 n} .

Beweis. Der Schaltkreis bzw. die Wahrscheinlichkeitsverteilung ist extrem einfach. Wir wählen zufällig einen Index

I \in {1, \dots, n}

und geben

x_{I}

als unseren Schaltkreis

C

(bestehend aus einem einzigen Input-Gate, das gleichzeitig das Output-Gate ist) aus. Dieser Schaltkreis ist natürlich monoton.

Beachten Sie, dass ich den Index groß geschrieben mit $I$ bezeichne, nicht $i$ ; das ist Konvention, weil $I$ eine Zufallsvariable ist. Sei nun ein festes $x \in {0, 1}$ gegeben. Mit welcher Wahrscheinlichkeit ist unser (recht primitiver) Schaltkreis korrekt?

\begin{aligned} C (x) & = {Maj}_{n} (x) ⟺ \\ x_{I} & = {Maj}_{n} (x) . \end{aligned}

Wir unterscheiden nun zwei Fälle. Wenn

{Maj}_{n} (x) = 1

ist, dann gibt es mindestens

k + 1

Indizes

i

mit

x_{i} = 1

. Wenn wir mit

I

einen solchen ausgewählt haben, dann sind wir erfolgreich. Die Wahrscheinlichkeit hierfür ist

\begin{aligned} \underset{C \sim C_{0}}{Pr} [C (x) = 1] = \underset{I \in [n]}{Pr} [x_{I} = 1] & = \frac{| {i \in [n] | x_{i} = 1}}{n} \geq \frac{k + 1}{n} \\ = \frac{k + 1}{2 k + 1} = \frac{k + \frac{1}{2} + \frac{1}{2}}{2 k + 1} \\ = \frac{1}{2} + \frac{1}{2 n} . \end{aligned}

Wenn nun

{Maj}_{n} (x) = 0

ist, dann gibt es mindestens

k + 1

Stellen

i

mit

x_{i} = 0

, und somit ist

C (x)

auch wieder mit Wahrscheinlichkeit mindestens

\frac{k + 1}{n + 1}

korrekt.

◻

Um eine Analogie aus dem Alltag zu bemühen: wenn Sie für eine Wahlprognose einen zufällig ausgewählten Bürger befragen, so ist das Ergebnis zwar nicht wirklich repräsentativ, aber immerhin leicht besser, als wenn Sie einfach raten würden. Unser zufälliger Schaltkreis sendet uns also ein schwaches aber positives Signal in die richtige Richtung. Die Signalstärke ist $\frac{1}{n}$ .

Die zweite Zutat ist nun ein "Signalverstäker". Angenommen, eine Verteilung $C$ hat Signalstärke $δ$ , also $\forall x \in {0, 1}^{n} : \underset{C \sim C}{Pr} [C (x) = {Maj}_{n} (x)] \geq \frac{1 + δ}{2} .$ Dann können wir drei Schaltkreise $C_{1}, C_{2}, C_{3} \sim C$ unabhängig voneinander samplen und einen neuen Schaltkreis bauen: $C^{'} (x) := {Maj}_{3} (C_{1} (x), C_{2} (x), C_{3} (x))$ . Dies gibt uns wiederum eine Verteilung über Schaltkreise, die wir $C^{\otimes 3}$ nennen. Diese hat eine höhere Signalstärke:

Lemma 2.5.8 Falls

C

eine Verteilung über Schaltkreise der Tiefe

d

und Größe

s

ist und

C

Signalstärke

δ

hat, dann gilt:

alle Schaltkreise in $C^{\otimes 3}$ haben Tiefe $d + 2$ ;
alle Schaltkreise in $C^{\otimes 3}$ haben Größe $3 s + 4$ ;
die Signalstärke von $C^{\otimes 3}$ ist $\frac{3}{2} δ - \frac{1}{2} δ^{3}$ .

Beweis. Wir betrachten ein festes $x \in {0, 1}^{n}$ mit ${Maj}_{n} (x) = 1$ ; der Fall ${Maj}_{n} (x) = 0$ ist analog. Wir definieren nun $U := C_{1} (x)$ , $V := C_{2} (x)$ und $W := C_{3} (x)$ . Da $C_{1}, C_{2}, C_{3} \sim C$ zufällige Schaltkreise sind, sind $U, V, W$ Zufallsvariable über ${0, 1}$ , und zwar unabhängig, weil wir $C_{1}, C_{2}, C - 3$ auch unabhängig gesampelt haben. Wir wissen: $Pr [U = 1] = Pr [V = 1] = Pr [W = 1] \geq \frac{1 + δ}{2} =: p$ . Was ist nun $Pr [{Maj}_{3} (U, V, W) = 1]$ ?

\begin{aligned} Pr [{Maj}_{3} (U, V, W) = 1] & = Pr [U = V = W = 1] + Pr [genau zwei von {U, V, W} sind 1] \\ = p^{3} + 3 p^{2} (1 - p) = {(\frac{1 + δ}{2})}^{3} + 3 {(\frac{1 + δ}{2})}^{2} \frac{1 - δ}{2} \\ = \frac{1}{8} (4 + 6 δ - 2 δ^{3}) \\ = \frac{1}{2} (1 + \frac{3}{2} δ - \frac{1}{2} δ^{3}) . \end{aligned}

Die Signalstärke von $C^{\otimes 3}$ ist also mindestens $\frac{3}{2} δ - \frac{1}{2} δ^{3}$ . $◻$

Wir beginnen nun mit der Verteilung $C_{0}$ über Schaltkreise der Größe 1 und definieren

\begin{array}{r} C_{i + 1} := (C_{i})^{\oplus 3} . \end{array}

Zur Wiederholung: um $C \sim C_{i + 1}$ zu sampeln, sampeln wir unabhängig drei Schaltkreise $\sim C_{i}$ und verknüpfen deren Output-Gates mit einem ${Maj}_{3}$ -Gadget. Wenn $C_{i}$ die Signalstärke $δ_{i}$ hat, dann hat $C_{i + 1}$ Signalstärke $\frac{3}{2} δ_{i} - \frac{1}{2} δ_{i}^{3}$ . Wenn $δ_{i} \leq 1 / 2$ sein sollte, dann ist das mindestens $\frac{5}{4} δ_{i}$ . Daraus folgt, dass nach höchstens $i^{*} := \log_{5 / 4} n$ Rekursionsstufen eine Signalstärke von mindestens $1 / 2$ erreicht ist: $C_{i^{*}}$ hat Signalstärke mindestens $1 / 2$ .

Wenn wir jetzt die rekursive Konstruktion fortsetzen, steigt die Signalstärke weiter an und konvergiert gegen $1$ : $lim_{i \to \infty} δ_{i} = 1$ . Die Frage ist nur, wie schnell konvergiert es? Da wir nun nicht mehr an Wahrscheinlichkeiten interessiert sind, die knapp über $1 / 2$ liegen, sondern an solchen, die knapp unter $1$ liegen, führen wir einen Parameterwechsel durch: eine Verteilung $C$ von Schaltkreisen mit Inputs $x_{1}, \dots, x_{n}$ hat Fehlerwahrscheinlichkeit $ϵ$ , wenn

\begin{array}{r} \forall x \in {0, 1}^{n} : \underset{C \sim C}{Pr} [C (x) = {Maj}_{n} (x)] \geq 1 - ϵ . \end{array}

Eine Signalstärke von $δ$ entspricht einer Fehlerwahrscheinlichkeit von $\frac{1 - δ}{2}$ . Die Verteilung $C_{i^{*}}$ hat also eine Fehlerwahrscheinlichkeit von höchstens $\frac{1 - 1 / 2}{2} = 1 / 4$ . Das obige Lemma, nun aus der Sicht der Fehlerwahrscheinlichkeit, liest sich so:

Behauptung. Wenn $C$ Fehlerwahrscheinlichkeit $ϵ$ hat, dann hat $C^{\otimes 3}$ Fehlerwahrscheinlichkeit $3 ϵ^{2}$

Beweis. Wie im Beweis vom Lemma setzen wir $p := \frac{1 + p}{2} = 1 - ϵ$ und erhalten

\begin{aligned} Pr [{Maj}_{3} (U, V, W) = 1] & = p^{3} + 3 p^{2} (1 - p) = (1 - ϵ^{3}) + 3 (1 - ϵ)^{2} ϵ = 1 - 3 ϵ^{2} . \end{aligned}

Somit hat $C^{\otimes 3}$ Fehlerwahrscheinlichkeit $3 ϵ^{2}$ . $◻$

Für $i^{*} := \log_{5 / 4} n$ hat $C_{i^{*}}$ eine Fehlerwahrscheinlichkeit von höchstens $1 / 4$ . Für $i^{*} + 1$ wird das zu $3 {(\frac{1}{4})}^{2} = \frac{3}{16}$ und für $i^{*} + 2$ zu $3 {(\frac{3}{16})}^{2} = \frac{27}{256} \leq \frac{1}{9}$ . Wenn nun $ϵ \leq \frac{1}{9}$ ist, dann gilt $3 ϵ^{2} \leq ϵ^{3 / 2}$ . Wir definieren $ϵ_{i} := \frac{1 - δ_{i}}{2}$ , also die Fehlerwahrscheinlichkeit von $C_{i}$ . Es gilt also $ϵ_{i + 1} \leq (ϵ_{i})^{3 / 2}$ für alle $i \geq i^{*} + 2$ und somit

\begin{array}{r} ϵ_{i^{*} + 2 + j} \leq {(ϵ_{i^{*}})}^{{(\frac{3}{2})}^{j}} \leq {(\frac{1}{4})}^{{(\frac{3}{2})}^{j}} . \end{array}

Qualitativ sehen wir: solange $δ_{i} \leq 1 / 2$ gilt, wächst die Signalstärke exponentiell an. Dieses exponentielle Wachstum kann natürlich nicht beliebig weitergehen. Jenseits $δ_{i} \leq 1 / 2$ hört das auf, dafür fällt nun die Fehlerwahrscheinlichkeit doppelt exponentiell. Für $j^{*} := \log_{3 / 2} n$ gilt dann

\begin{array}{r} ϵ_{i^{*} + 2 + j^{*}} \leq {(\frac{1}{4})}^{n} < 2^{- n} . \end{array}

In Bildern:

Graph der Funktion

p \mapsto p^{3} + 3 p^{2} (1 - p)

Signalstärke

δ

wächst für

p \in [1 / 2, 3 / 4]

exponentiell.

Fehlerwahrscheinlichkeit

ϵ

fällt für

p \in [3 / 4, 1 / 2]

doppelt exponentiell.

Wir setzen nun $k := i^{*} + 2 + j^{*} = \log_{5 / 4} n + 2 + \log_{3 / 2} n = O (\log n)$ und sehen, dass $C_{k}$ eine Verteilung über Schaltkreise mit Tiefe $O (\log n)$ und Fehlerwahrscheinlichkeit kleiner als $2^{- n}$ ist. Was nun kommt, ist ein absolutes Standardargument in probabilitischen Beweisen: ein Union Bound. Das geht ungefähr so: wenn für jedes feste $b \in {0, 1}^{n}$ ein Schaltkreis $C C_{k}$ mit Wahrscheinlichkeit $ϵ_{k}$ irrt, dann ist die Wahrscheinlichkeit, dass $C$ sich für irgendein $x \in {0, 1}^{n}$ irrt, höchstens $2^{n} ϵ_{k}$ . Formal: für jedes $b \in {0, 1}^{n}$ definieren wir $E_{b}$ als die Menge der Schaltkreise mit Input-Variablen $x_{1}, \dots, x_{n}$ , die sich auf $b$ irren, also

\begin{array}{r} E_{b} := {Schaltkreise C über x_{1}, \dots, x_{n} | C (b) \neq {Maj}_{n} (b)} . \end{array}

Die Verteilung $C_{k}$ existiert ja im Wahrscheinlichkeitsraum aller Boolescher Schaltkreise mit Inputs $x_{1}, \dots, x_{n}$ . Die Menge $E_{b}$ ist somit ein Ereignis in diesem Raum. Ein extrem unwahrscheinliches Ereignis:

\begin{array}{r} \forall b \in {0, 1}^{n} : \underset{C \sim C_{k}}{Pr} [C \in E_{b}] = ϵ_{k} < 2^{- n} . \end{array}

Oder kompakt ausgedrückt: $\underset{C_{k}}{Pr} [E_{b}] < 2^{n}$ . Wir haben nun ein Ereignis $E_{b}$ für jedes $b \in {0, 1}^{n}$ und definieren

\begin{array}{r} E := ⋃_{b \in {0, 1}^{n}} E_{b} . \end{array}

Was ist $E$ ? Es ist die Menge der Schaltkreise, die sich auf mindestens einem $b \in {0, 1}^{n}$ irren. Was ist das Komplement $\bar{E}$ ? Das ist die Menge der Schaltkreise, die sich auf keinem $b \in {0, 1}^{n}$ irren, also die Menge der Schaltkreise, die ${Maj}_{n}$ korrekt berechnen. Es gilt nun

\begin{aligned} \underset{C_{k}}{Pr} [E] & = \underset{C_{k}}{Pr} [⋃_{b \in {0, 1}^{n}} E_{b}] \\ \leq \sum_{b \in {0, 1}^{n}} \underset{C_{k}}{Pr} [E_{b}] \\ = \sum_{b \in {0, 1}^{n}} ϵ_{k} \\ < \sum_{b \in {0, 1}^{n}} 2^{- n} = 2^{n} 2^{- n} = 1 . \end{aligned}

Also $\underset{C_{k}}{Pr} [E] < 1$ und somit $\underset{C_{k}}{Pr} [\bar{E}] > 0$ . Das bedeutet, dass ein zufälliger Schaltkreis $C \sim C_{K}$ mit positiver Wahrscheinlichkeit die Funktion ${Maj}_{n}$ korrekt berechnet. Jeder Schaltkreis, der unter $C_{k}$ gesampelt werden kann, hat Tiefe $O (\log n)$ , Fan-in 2 und ist monoton, und somit schließen wir: es gibt einen monotonen Schaltkreis $C$ mit Fan-in 2 und Tiefe $O (\log n)$ , der ${Maj}_{n}$ berechnet.

Es bleibt die Frage, wie groß dieser Schaltkreis $C$ ist. Seien wir hier bequem: ein Schaltkreis mit Fan-in 2 und einem Output-Gate hat höchstens $2^{i}$ Gates, die Abstand $i$ vom Output-Gate haben. Somit hat ein Schaltkreis mit Fan-in 2 und Tiefe $d$ höchstens

\begin{array}{r} 1 + 2 + 4 + \dots + 2^{d} = 2^{d + 1} - 1 \end{array}

Gates. Ein Schaltkreis mit Fan-in 2 und Tiefe $c \log_{2} n$ hat also insgesamt höchstens $2^{c \log n + 1} - 1 = O (n^{c}) = O (poly (n))$ Gates. $◻$

Übungsaufgabe 2.5.5 Präzisieren Sie die Größe von Valiants Schaltkreis und bestimmen ein $c \in R$ , so dass er die Größe $Θ (n^{c})$ hat.

Wir könnten nun noch ehrgeiziger sein und einen monotonen Schaltkreis mit Fan-in 2, Tiefe $O (\log n)$ und linearer Größe $O (n)$ anstreben.

2.5 Majority

Majority Top-Down mit if-then-else-Gates

Majority durch Zählen

O(log⁡n) Tiefe mit 2-for-3-Addierern.

Monoton und polylogarithmische Tiefe durch Halbierung und Aufzählung.

Monoton und logarithmische Tiefe: Valiants probabilitische Konstruktion

Majority Top-Down mit `if-then-else`-Gates

$O (\log n)$ Tiefe mit 2-for-3-Addierern.