2.6 Untere und obere Schranken

Wir haben zwei Methoden gesehen, zu einer beliebigen Booleschen Funktion $f : {0, 1}^{n} \to {0, 1}$ einen Booleschen Schaltkreis zu konstruieren: top-down, indem wir $f$ in $f_{0}$ und $f_{1}$ zerlegen und mit Hilfe eines if-then-else-Gates wieder zusammenfügen; und bottom-up als DNF oder CNF. Die so entstandenen Schaltkreise hatten Größe $O (2^{n})$ (bzw. $O (n 2^{n})$ wenn wir zuerst eine CNF oder DNF bauen und dann auf Fan-in 2 bestehen). Die offensichtliche Frage: geht es besser? Die Antwort: Ja, aber nicht viel besser.

Theorem 2.6.1 (Shannon). Es gibt Boolesche Funktionen $f$ , die keine Schaltkreise kleiner als $Ω (2^{n} / n)$ haben.

Beweis. Die Beweismethode ist vielleicht neu für Sie, aber in der Komplexitätstheorie und Kombinatorik sehr wichtig. Wir stellen uns zwei Zählaufgaben: (1) wie viele Boolesche Funktion $f : {0, 1}^{n} \to {0, 1}$ gibt es? (2) Wie viele Boolesche Schaltkreise mit $n$ Input-Variablen, Fan-in 2 und $s$ Gates gibt es? Wenn die Antwort auf (2) kleiner ausfällt als auf (1), dann können nicht alle Booleschen Funktionen mit $n$ Variablen einen Schaltkreis mit weniger als $s$ Gates haben. Es gibt einfach nicht genug für alle. Dahinter steht folgende Beobachtung: zwei verschiedene Boolesche Funktionen brauchen verschiedene Schaltkreise; sie können sich nicht einen "teilen" (dieses Behauptung erscheint trivial und ist es auch; machen Sie sich aber klar, dass wir diese Eigenschaft benötigen, falls Sie nämlich ein Abzählargument in anderen Kontexten anwenden).

Die Antwort auf (1) ist einfach: es gibt genau $2^{2^{n}}$ Boolesche Funktionen mit $n$ Variablen. Warum? Die Wahrheitstabelle hat $2^{n}$ Zeilen. Sie könnne sich also $2^{n}$ mal für $0$ oder $1$ entscheiden.

Behauptung Sei $s \geq n \geq 1$ . Dann gibt es höchstens $s^{2 s + 1}$ Schaltkreise mit $n$ Input-Variablen, Fan-in 2 und $s$ Gates.

Beweis. Wir bauen den Schaltkreis, indem wir erst einmal $s$ Gates unbeschriftet "hinmalen". Um nun zu entscheiden, was für ein Schaltkreis das sein soll, müssen wir Entscheidungen treffen:

Für jedes der $s$ Gates, was es sein soll.
- Ein Input-Gate? Dann müssen wir es mit einer der $n$ Input-Variablen beschriften.
- Ein Not-Gate? Dann müssen wir eines der anderen Gates als Vorgänger-Gate wählen. Wir haben höchstens $s - 1$ Möglichkeiten.
- Ein And-Gate? Dann müssen wir zwei der anderen Gates als Vorgänger-Gates wählen. Wir haben höchstesn $(\binom{s - 1}{2}) = \frac{(s - 1) (s - 2)}{2}$ Möglichkeiten.
- Ein Or-Gate? Dann haben wir auch höchstens $(\binom{s - 1}{2})$ Möglichkeiten.
Insgesamt haben wir also $n + (s - 1) + 2 (\binom{s - 1}{2}) = n + s - 1 + (s - 1) (s - 2) = n + s^{2} - 2 s + 1 \leq s^{2}$ Möglichkeiten.
Für den gesamten Schaltkreis: welches Gate Output-Gate sein soll. Da haben wir $s$ Möglichkeiten.

Um die Gesamtzahl der Möglichkeiten abzuschätzen, müssen wir das alles multiplizieren. Wir haben höchstens

\underset{Output-Gate wählen}{\underset{⏟}{s}} \cdot \underset{jedes Gate beschriften}{\underset{⏟}{\prod_{i = 1}^{s} (s^{2})}} = s \cdot (s^{2})^{s} = s^{2 s + 1}

Möglichkeiten. Es gibt also höchstens

s^{2 s + 1}

verschiedene Schaltkreise mit

s

Gates, Fan-in 2 und

n

Variablen.

◻

Wählen wir nun $s := 2^{n} / (2 n)$ . Wieviele Schaltkreise mit $n$ Variablen, Fan-in 2 und $s$ Gates gibt es? Die Schranke in der obigen Behauptung sagt, dies seien höchstens

\begin{aligned} {(\frac{2^{n}}{2 n})}^{\frac{2^{n}}{n} + 1} & = {(2^{n - \log (2 n)})}^{\frac{2^{n}}{n} + 1} \\ = 2^{2^{n} + n - \log (2 n) \frac{2^{n}}{n} - \log (2 n)} \\ < 2^{2^{n}} . \end{aligned}

Also: es gibt mehr Boolesche Funktionen in $n$ Variablen, als es Boolesche Schaltkreise mit $\frac{2^{n}}{2 n}$ Gates gibt. Somit benötigen manche Boolesche Funktionen mehr als $\frac{2^{n}}{2 n}$ Gates. $◻$

Übungsaufgabe 2.6.1 In Theorem und Beweis sprechen wir die ganze Zeit nur von Schaltkreisen mit Fan-in 2. Was geschieht, wenn wir beliebigen Fan-in erlauben? Wie ändern sich Aussage und Beweis?

Was geschieht, wenn wir weitere Gates, z.B. $\oplus$ als atomare Gates zulassen?

Der obige Beweis sagt noch mehr: der Anteil Boolescher Funktionen, bei denen wir mit $\frac{2^{n}}{2 n}$ Gates auskommen, ist verschwindend klein. Fast alle Funktionen brauchen also riesige Schaltkreise. In einem Gewissen Sinne haben wir also einfach Glück: die Funktionen, die uns interessieren, wie -Bit-Addition, Majority, Parity und so weiter, haben einfach niedrige Komplexität. Das liegt wohl in der Natur der Sache: wir addieren, multiplizieren, bauen Brücken, Häuser, Flugzeuge, Computer, weil wir es können, weil also die dafür benötigten Berechnungen effizient durchführbar sind.

Forschungsprojekt. Finde eine konkret beschreibbare Funktion , die exponentiell viele (oder zumindest superpolynomiell viele) Gates benötigt.

Kandidaten für solche Funktionen gibt es viele. Im Prinzip gibt uns jedes Entscheidungsproblem, dass für eine "schwierige" Komplexitätsklasse vollständig ist, einen Kandidaten. Also zum Beispiel Graphenfärbbarkeit.

Entscheidungsproblem 3-Färbbarkeit. Gegeben ein Graph , gibt es eine Funktion

so dass für alle gilt? Dass also benachbarte Knoten verschiedene Farben bekommen?

3-Färbbarkeit ist ein zentrales NP-vollständiges Problem. Wir vermuten also, dass es dafür keinen polynomiellen Algorithmus gibt. Wir können es zur Zeit (April 2024) aber nicht beweisen. Dies ist das berühmte Problem P vs NP, von dem Sie sicher schon gehört haben und das als eines der großen offenen Probleme der Mathematik insgesamt gilt. Die Frage, ob NP-Probleme polynomiell große Schaltkreise haben, ist noch offener.

Übungsaufgabe 2.6.2 Formal gesehen ist Graphenfärbbarkeit eine Sprache über einem Alphabet , dass uns erlaubt, Graphen zu codieren. Wie können wir als Boolesche Funktion darstellen?

Obere Schranken: Die Lupanov-Schranke

Wir haben nun eine Konstruktion, die uns für jede beliebige Funktion Schaltkresie mit Gates baut. Wir haben eine untere Schranke, die besagt, dass es mit weniger als Gates nicht geht. Diese beiden Schranken lassen aber immer noch eine Lücke der Größenordnung . Können wir sie schließen?

Theorem 2.6.2 (Lupanov). Für jede Boolesche Funktion in Variablen gibt es einen Schaltkreis mit Fan-in 2 und Gates.

Beweis. Der Beweis fußt auf zwei Kernideen: erstens bauen wir den Schaltkreis nicht mit AND- und OR- und NOT-Gates, sondern mit AND- und XOR-Gates. Da wir nach vollendeter Konstruktion jedes XOR-Gates durch einen kleinen Schaltkreis aus vier AND/OR/NOT-Gates ersetzen können, spielt dies keine Rolle (der Faktor 4 verschwindet in der -Notation).

Die zweite Idee ist, dass wir anstreben, für eine bliebige Menge an Booleschen Funktionen einen "überraschend guten" Schaltkreis zu bauen, der jede Funktion berechnet. Dieser Schaltkreis wird Output-Gates haben, und seine Größe wird auch von abhängen.

-Polynome. Polynome in mehreren Variablen kennen Sie sicherlich: zum Beispiel . Der Unterschied hier ist nur, dass wir alle Werte modulo 2 auswerten, also in dem endlichen Körper arbeiten. Wir brauchen daher auch keine höheren Potenzen: und ergeben für alle die gleichen Werte. Wenn wir in rechnen, können wir uns also auf multilineare Polynome beschränken. Führen wir Polynome formal ein: wir haben eine Menge von Variablen; ein Monom in diesem Variablen ist ein Produkt aus Variablen, also für eine Menge . Wir schreiben das kurzerhand als . Ein Polynom ist nun eine Summe von Monomen: . Beachten Sie, dass wir vor den Monomen keine Koeffizienten brauchen, da es als Konstanten eh nur 0 und 1 gibt. Ein Polynom berechnet eine Boolesche Funktion .

Übungsaufgabe 2.6.3 Zeigen Sie, dass sich jede Boolesche Funktion als -Polynom schreiben lässt.

Tipp: beschränken Sie sich zuerst auf Funktionen , deren Wahrheitstabelle in genau einer Zeile eine 1 haben. Schreiben Sie eine solche Funktion als -Polynom.

Wann sind zwei Polynome gleich? Wenn sie die gleichen Monome haben (mit gleichen Koeffizienten, aber die spielen hier ja keine Rolle). Wir würden also sagen, dass und die gleichen Polynome sind. Dagegen wären und verschiedene Polynome. Da wir über arbeiten, beschränken wir uns aber eh auf multilineare Polynome, wo also alle Exponenten 1 sind.

Übungsaufgabe 2.6.4 Zeigen Sie, dass sich jede Funktion eindeutig als multilineares -Polynom schreiben lässt. In anderen Worten: wenn und zwei verschiedene multilineare Polynome sind, dann berechnen sie verschiedene Funktionen.

Ein -Polynom können wir natürlich ganz einfach als Schaltkreis mit AND- und XOR-Gates schreiben. AND für die Multiplikation und XOR für die Addition in . Dies ist also die erste Kernidee: wir arbeiten mit AND und XOR und somit mit -Polynomen. Wieviele Gates brauchen wir dafür?

Schreiben wir . Ein Monom können wir mit AND-Gates berechnen. Die Summe bilden wir mit weiteren XOR-Gates. Da und gilt, brauchen wir maximal

Gates. Allerdings ist das eine ungenaue Rechnung: Selbst wenn alle Monome vertreten sind, bestehen nicht alle Monome aus Variablen.

Übungsaufgabe 2.6.5 Rechnen Sie genauer! Wenn Sie alle Monome berechnen wollen, brauchen Sie

viele AND-Gates. Finden Sie eine geschlossene Formel für diesen Ausdruck.

Als nächstes wollen wir zeigen, wie man mit höchstens AND-Gates und XOR-Gates berechnet. Wir zeigen in der Tat etwas mehr:

Lemma 2.6.3 Es gibt einen Schaltkreis mit Input-Gates und Output-Gates, eines für jedes Monom , der Gates hat.

Beweis. Die Idee ist: wenn wir berechnen wollen, brauchen wir drei AND-Gates. Allerdings müssen wir eh berechnen, da wir ja alle Monome wollen. Wenn wir also einen Schaltkreis für haben, können wir daraus mit einem zusätzlichen AND-Gate berechnen.

Formal geht es mit Induktion über . Für haben wir ein einziges Monom, nämlich , und einen Schaltkreis mit einem einzigen Gate: dem Konstant-1-Gate, das gleichzeitig ein Output-Gate ist. Für bauen wir zuerst per Induktion einen Schaltkreis , der alle Monome für berechnet. Um zu bauen, schaffen wir für jedes ein AND-Gate, das berechnet.

Insgesamt erhalten wir

Gates, von denen jedes gleichzeitig ein Ouptut-Gate ist.

Die zweite Kernidee ist, dass Synergien auftreten, dass wir die Variablen in einen vorderen und in einen hinteren Teil aufteilen: die erste Variablen benennen wir um in ; die hinteren Variablen in . Wir können also wie folgt schreiben:

Die obige Summe beinhaltet also Terme von der Form . Es gibt insgesamt nur Polynome in den Variablen . Wenn nun also ist, werden gewisse Polynome mehrfach auftreten, und wir können sparen. Dafür berechnen wir vorsorglich alle Funktionen in .

Lemma. Es gibt einen Schaltkreis mit Input-Gates und Output-Gates, einen für jede Funktion . Der Schaltkreis hat Fan-in 2 und insgesamt Gates (AND-Gates und XOR-Gates).

Übungsaufgabe 2.6.6 Beweisen Sie das Lemma. Konstrukieren Sie zuerst wie im vorherigen Lemma einen Schaltkreis, der Ihnen alle Monome berechnet.

Übungsaufgabe 2.6.7 Zeigen Sie, dass die obige Konstruktion verbessert werden kann, indem Sie einen Schaltkreis mit nur Gates bauen.

Tip. Jedes Gate muss also gleichzeitig ein Output-Gate sein.

Wenn wir nun einen Schaltkreis haben, der uns jedes berechnet, schauen wir uns wieder an.

Für jedes haben wir ja bereits ein Gate, das es berechnet. Mit einem weiteren Schaltkreis von Gates können wir alle Monome berechnen. Schlussendlich müssen wir noch die Summe bilden, wofür wir XOR-Gates brauchen. Insgesamt brauchen wir also

Wir müssen nun so wählen, dass der obige Ausdruck minimiert wird. Anstatt nun abzuleiten und gleich 0 zu setzen, verwenden wir einen Faulheitstrick, der funktioniert, wenn Sie das Minimum nur ungefähr haben wollen: wir setzen so, dass die beiden großen Ausdrücke - und ungefähr gleich sind. Das gibt nicht das präzise Minimum, aber sicherlich eine gültige Konstruktion und somit eine obere Schranke.

Ich habe keine explizite Formel, um das für aufzulösen, also setze ich auf gut Glück und wir erhalten

und wir können gleich aufhören, da der erste Term bereits ergibt. Das ist zu groß. Wir müssen also kleiner wählen. Nächster Versuch: .

Das ist die behauptete Schranke.