Überblick über Razborovs Approximationsmethode auf hoher Ebene

Was ist Razborovs Approximationsmethode? Kann jemand einen Überblick auf hoher Ebene und die Intuition dahinter geben?

Sei $f$ eine Boolesche Funktion für $n$ Bits. Sei $Z = f^{-1}(0) \subseteq 2^n$ . Sei $C$ eine Schaltung auf n Bits und der Größe $m$ und der Gates $g_1, \ldots, g_m$ . $g_i$ bezeichnet auch die Funktion auf $n$ Bits, die durch eine Teilschaltung mit $g_i$ als letztem Gate berechnet wurden . Die ersten $n$ Gatter sind für den Eingang $x_1, \ldots, x_n$. Das Ziel ist zu zeigen, dass der Größe m f nicht berechnen kann . Betrachten wir alle Berechnungen von C auf Eingaben von Z . Eine Berechnung weist den Ausgängen von Gates Werte zu. Sei B die Boolesche Algebra von P ( Z ) .$C$$m$$f$$C$$Z$$B$$P(Z)$

Die Idee ist, für jede Funktion auf n- Bits zu berücksichtigen, wie gut sie sich f auf Z annähert . Lassen Sie | | g | | = { w ∈ Z ∣ g ( w ) ≠ 0 } .$g$$n$$f$$Z$$||g|| = \{w \in Z \mid g(w) \neq 0 \}$

Für einen Ultrafilter wir daraus eine neue Berechnung durch Ultraprodukt definieren: c ( g i ) = 0 iff | | g i | | ∉ F . Da ein Ultrafilter im Wesentlichen eine Reihe konsistenter Berechnungen für 0-Werte ist, ist das resultierende c eine gültige Berechnung. Daraus folgt, dass f ( c 1 , … , c n ) = 0 ist . Wir haben eine neue Berechnung aus vorhandenen erstellt. Da alle Ultrafilter auf endlichen Mengen Prinzip $F \subseteq B$$c(g_i) = 0$$||g_i|| \not\in F$$c$$f(c_1, \ldots, c_n) = 0$ . Dies funktioniert für jede Schaltung, wir haben die Tatsache nicht ausgenutzt, dass die Schaltung die Größe m hat .$c_1,\ldots,c_n \in Z$$m$

Die nächste Idee besteht nun darin, die Endlichkeit der Schaltung auszunutzen, um einen neuen Eingang zu konstruieren, der außerhalb von und f ( w ) ≠ 0 liegt. Die Schaltung bemerkt dies jedoch aufgrund ihrer begrenzten Größe nicht und gibt daher immer noch 0 aus. Sie berechnet also nicht f .$Z$$f(w) \neq 0$$f$

Wir müssen die Definition des Ultrafilters lockern, damit wir eine Eingabe außerhalb von . Anstelle von Ultrafiltern verwenden wir nach oben geschlossene Teilmengen von B ( a ∈ F und a ⊆ b impliziert b ∈ F ), die erhalten bleiben ( a , b ∈ F impliziert a ∩ b ∈ F ).$Z$$B$$a \in F$$a \subseteq b$$b \in F$$a,b \in F$$a \cap b \in F$

Sei . W F ist die Menge der Eingänge, die mit F übereinstimmen . Wenn F eine Primzahl ist ( a ∪ b ∈ F impliziert a ∈ $W_F = \{w \in 2^n \mid w_i = 0 \to ||\lnot x_i|| \in F, w_i \neq 0 \to ||x_i|| \in F\}$$W_F$$F$$F$$a \cup b \in F$$a \in F$oder ) und nonfull ( ∅ ∉ F ) dann für jedes i , F enthält entweder | | x i | | oder | | ¬ x i | | und W F enthält nur eine einzige Eingabe.$b \in F$$\emptyset \not\in F$$i$$F$$||x_i||$$||\lnot x_i||$$W_F$

Wir werden die Erhaltung der Treffen entspannen. Anstelle aller Treffen in der Booleschen Algebra werden wir eine kleine Anzahl von ihnen bewahren. Lassen Sie sei die kleinste Zahl k von erfüllt M = ( a 1 ∩ b 1 , … , a k ∩ b k ), so dass für alle nach oben geschlossenen, nicht vollen, M- konservierenden F , W F ⊆ Z gilt .$|f|$$k$$M = (a_1 \cap b_1, \ldots, a_k \cap b_k)$$M$$F$$W_F \subseteq Z$

Sei die Schaltungskomplexität von f . Razborov hat bewiesen, dass $m$$f$.$\frac{1}{2}|f| \leq m \leq O(|f|^3 + n^3)$

Beachten Sie, dass diese Ungleichung für alle Funktionen gilt. Um eine untere Grenze der Schaltungsgröße zu beweisen, zeigen Sie, dass es für alle m- Treffen M ein F gibt , das die Bedingungen erfüllt, aber sein W F nicht in Z enthalten ist . Darüber hinaus kann mit dieser Methode aufgrund der zweiten Ungleichung jede Untergrenze einer starken Schaltung nachgewiesen werden.$m$$m$$M$$F$$W_F$$Z$

Der eigentliche Teil eines Schaltungsunterbeweises besteht darin, zu zeigen, dass es für gegebenes für alle m- Treffen ein solches F gibt . Im Fall von monotonen Schaltungen vereinfacht sich die Bedingung um W F zu w i ≠ 0 → | | x i | | ∈ F, so dass es einfacher ist, F zu finden .$m$$m$$F$$W_F$$w_i \neq 0 \to ||x_i|| \in F$$F$

Alexander Razborov, Über die Methode der Approximation, 1989. pdf

Mauricio Karchmer, Über den Nachweis von Untergrenzen für die Schaltungsgröße, 1995.

Tim Gowers, Razborovs Approximationsmethode, 2009. pdf

Haftungsausschluss : Dies ist nur eine allgemeine Übersicht, die einen Einblick in die in Blums jüngstem Artikel verwendeten Methoden geben soll.

Ich werde versuchen, eine Notation zu verwenden, die näher an der in dem oben genannten Artikel verwendeten liegt.

Sei eine Boolesche Funktion für n Variablen x 1 , … , x n . Angenommen, wir möchten beweisen, dass jedes boolesche Netzwerkcomputer f eine große Größe hat.$f$$n$$x_1,\dots,x_n$$f$

Betrachten Sie den folgenden Prozess, wenn ein boolesches Netzwerk an seinem Ausgangsknoten f berechnet .$\beta$$f$

1. Ordnen Sie die Gates in gemäß einer topologischen Reihenfolge g 1 , g 2 , … , g m, wobei der letzte Knoten der Ausgabeknoten ist.$\beta$$g_1,g_2,\dots,g_m$
2. Für jeden Zeitschritt wir approximieren die Funktion am Gatter berechnet g t durch eine „einfache“ Funktion f g t . Diese Annäherung kann die an Knoten stromabwärts von g t berechneten Funktionen ändern (insbesondere kann sich die Funktion am Ausgangsknoten g m geändert haben).$t=1,\dots,m$$g_t$$f_{g_t}$$g_t$$g_m$

Am Ende dieses Prozesses haben wir die bei berechnete Funktion durch eine einfache Funktion f g m angenähert .$g_m$$f_{g_m}$

Als nächstes konstruiere eine Gruppe von Testeingaben .$T\subseteq \{0,1\}^n$

Angenommen, wir können die folgenden Aussagen beweisen:

• Die Annäherung jedes einzelnen Knotens ist gut (dh höchstens -many Fehler auf Eingaben von eingeführt T bei jedem Näherungsschritt).$e$$T$
• Keine einfache Funktion nähert sich gut an (dh für jede einfache Funktion f g m haben wir f g m ≠ f auf mehr als einer d- Fraktion von T ).$f$$f_{g_m}$$f_{g_m}\neq f$$d$$T$

Wenn wir dann einfach die Anzahl der Fehler zählen, erhalten wir, dass mindestens d | haben muss T $\beta$ viele Tore.$\tfrac{d\lvert T\rvert}{e}$

Wenn gezeigt werden kann, dass dieses Approximationsschema für jedes Netzwerk funktioniert , das die Funktion f berechnet , dann kommen wir zu einer Untergrenze für die Schaltungskomplexität von f .$\beta$$f$$f$