Untergrenzen der Formelgröße für AC0-Funktionen

Frage:

Was ist die bekannteste untere Grenze der Formelgröße für eine explizite Funktion in AC ⁰ ? Gibt es eine explizite Funktion mit einem $\Omega(n^2)$ unteren Grenze von ?

Hintergrund:

Wie die meisten Untergrenzen sind auch Untergrenzen für die Formelgröße schwer zu bekommen. Ich interessiere mich für untere Schranken der Formelgröße über dem Standard-Universal-Gate-Set {AND, OR, NOT}.

Die bekannteste untere Grenze der Formelgröße für eine explizite Funktion über diese Tormenge ist für eine von Andreev definierte Funktion. Diese Schranke wurde von Håstad aufgezeigt und die untere Schranke von Andreev von Ω ( n 2.5 - o ( 1 ) ) verbessert . Eine weitere explizite Untergrenze ist Khrapchenkos Ω ( n 2 ) -Untergrenze für die Paritätsfunktion.$\Omega(n^{3-o(1)})$$\Omega(n^{2.5-o(1)})$$\Omega(n^2)$

Diese beiden Funktionen befinden sich jedoch nicht in AC ⁰ . Ich frage mich, ob wir eine explizite Funktion in AC ⁰ mit einer quadratischen (oder besseren) Untergrenze kennen. Die beste Grenze, die mir bekannt ist, ist die untere Grenze von für die Elementunterscheidungsfunktion, wie von Nechiporuk gezeigt. Beachten Sie, dass sich die Elementunterscheidungsfunktion in AC ⁰ befindet. Daher suche ich nach einer Untergrenze für eine explizite AC ⁰ -Funktion, die besser ist als Ω ( n 2 / log n ) , vorzugsweise Ω ( n 2 ) .$\Omega(n^2/\log n)$$\Omega(n^2/\log n)$$\Omega(n^2)$

Weitere Lektüre:

Eine hervorragende Ressource zum Thema ist "Boolean Function Complexity: Advances and Frontiers" von Stasys Jukna. Ein Entwurf des Buches ist kostenlos auf seiner Website verfügbar.

Eine schöne Frage! Chrapchenko kann definitiv keine quadratischen Untergrenzen für -Funktionen angeben . Seine Untergrenze ist in der Tat mindestens ein Quadrat der durchschnittlichen Empfindlichkeit. Und alle Funktionen in A C 0 haben eine polylogarithmische Durchschnittsempfindlichkeit. Subbotovskaya-Andreev kann eine solche Funktion anscheinend auch nicht geben, weil das Argument, das sie verwenden (zufällige Einschränkung führt zu viel kleineren Formeln), genau der Grund ist, der eine große A C 0 -Schaltungsgröße erzwingt ; Hastads Umschalt-Lemma (bin mir nicht ganz sicher, nur eine Intuition). Die einzige Hoffnung ist Nechiporuk. Aber sein Argument kann nicht mehr als n 2 / log $AC^0$$AC^0$$AC^0$$n^2/\log n$aus informationstheoretischen Gründen. Kann es also sein, dass alles in $AC^0$ Formeln von quadratischer (oder sogar kleiner) Größe hat? Ich glaube nicht daran, konnte aber nicht schnell ein Gegenbeispiel finden.

Tatsächlich tritt das Allender-Koucky-Phänomen auch in einem anderen Kontext auf - in der Komplexität von Graphen. Angenommen, eine Schaltung von Variablen repräsentiert einen zweigeteilten n × n Graphen G auf Eckpunkten V = { 1 , … , 2 n }, wenn für jeden Eingangsvektor a mit genau zwei 1s beispielsweise die Positionen i und j ( i ≤ n) sind , j > n ) die Schaltung akzeptiert ein iff Vertices i und$2n$$n\times n$$G$$V=\{1,\ldots,2n\}$$a$$i$$j$$i\leq n$$j>n$$a$$i$$j$sind in benachbart . Problem: Zeigen Sie einen expliziten Graphen G , bei dem mindestens n ϵ Gatter durch eine monotone Σ 3 -Schaltung dargestellt werden müssen. Es scheint wie eine unschuldige Frage (da die meisten Graphen benötigen etwa n 1 / 2 Tore. Aber eine solche Graphen uns eine Boolesche Funktion von würde 2 m = 2 log n Variablen erfordern nicht-monotone log-Tiefe Schaltungen von superlinear Größe (durch die Ergebnisse Valiant). Daher kann es eine Herausforderung sein, n ϵ untere Schranken für Schaltkreise der Tiefe 3 zu beweisen . $G$$G$$n^{\epsilon}$ $\Sigma_3$$n^{1/2}$$2m=2\log n$$n^{\epsilon}$

Vielen Dank, Kaveh, dass Sie sich Kapitel über die Komplexität von Beweisen ansehen möchten!

In Bezug auf Robins Frage enthält zuerst diese Note Funktionen, die Formeln (und sogar Schaltkreise) der Größe n k für jede Konstante k erfordern . Dies folgt beispielsweise aus einer einfachen Tatsache, dass A C 0 alle DNFs mit konstant langen Monomen enthält. Somit enthält A C 0 mindestens exp ( n k ) verschiedene Funktionen für jedes k . Andererseits haben wir höchstens ungefähr exp ( t log n ) -Funktionen, die durch Formeln der Größe t berechenbar sind$AC^0$ $n^k$$k$$AC^0$$AC^0$$\exp(n^k)$$k$$\exp(t\log n)$$t$.

Ich habe kurz mit Igor Sergeev (von der Moskauer Universität) über die Frage diskutiert, wie man explizite untere Schranken von oder größer bekommt . Eine Möglichkeit könnte darin bestehen, die Methode von Andreev zu verwenden, diese jedoch auf eine andere, besser berechenbare Funktion anzuwenden, anstatt auf Parity. Das heißt, man betrachte eine Funktion von n Variablen der Form F ( X ) = f ( g ( X 1 ) , ... , g ( X b ) ), wobei b = log n und g eine Funktion in $n^2$$n$$F(X)=f(g(X_1),\ldots,g(X_b))$$b=\log n$$g$ von n / b Variablen; f ist eine der komplexesten Funktionen von b- Variablen (die bloße Existenz von f reicht aus). Wir brauchen nur, dass die Funktion g nicht im folgenden Sinne "getötet" werden kann: Wenn wir alleVariablenaußer k in X fixieren, muss es möglich sein, alle bis auf eine der verbleibenden Variablen von g zu fixieren,so dass die erhaltene Unterfunktion von g erhalten wird ist eine einzelne Variable. Dann Aufbringen Andreev Arguments und Hastad Ergebnis verwendetdass der schrumpfende Konstante ist mindestens 2 (nicht nur 3 /$AC^0$$n/b$$f$$b$$f$$g$$k$$X$$g$$g$$2$$3/2$wie zuvor von Sybbotovskaya gezeigt), wird die resultierende Untergrenze für ungefähr n 3 / k 2 sein . Natürlich wissen wir, dass jede Funktion in A C 0 beendet werden kann , indem alle Variablen außer n 1 / d für eine Konstante d ≥ 2 festgelegt werden . Aber um eine n 2 untere Grenze es ausreichen würde , eine explizite Funktion in finden A C 0 , die nicht von allen Befestigungs getötet werden kann , sondern, sagen wir, n 1 /$F(X)$$n^3/k^2$$AC^0$ $n^{1/d}$$d\geq 2$$n^2$$AC^0$$n^{1/2}$Variablen. Man sollte nach einer solchen Funktion in einer Tiefe suchen, die größer als zwei ist.

Tatsächlich kann man für die Funktion wie oben durch einfaches gieriges Argument, kein Nechiporuk, keine Subbotovskaya und keine zufälligen Beschränkungen untere Grenzen um n 2 / log n erhalten ! Hierzu reicht es lediglich aus, dass die "innere Funktion" g (Y) nicht trivial ist (hängt von all ihrem n /$F(X)$$n^2/\log n$$n/b$ Variablen). Darüber hinaus gilt die Grenze für jede Basis konstanter Fan-Gates, nicht nur für De Morgan-Formeln.

Beweis: Ausgehend von einer Formel für mit s Blättern wählen Sie in jedem Block X i eine Variable aus, die am seltensten als Blatt vorkommt. Setzen Sie dann alle verbleibenden Variablen auf die entsprechenden Konstanten, sodass jedes g ( X i ) zu einer Variablen oder ihrer Negation wird. Die erhaltene Formel ist dann mindestens n / b- mal kleiner als die ursprüngliche Formel. Somit ist s mindestens n / b = n / log $F(X)$$s$$X_i$$g(X_i)$$n/b$$s$$n/b=n/\log n$mal die Formelgröße von f , dh s ≥ n 2 - o ( 1 $2^b/\log b=n/\log\log n$$f$$s\geq n^{2-o(1)}$ . QED

Um oder mehr zu erhalten, muss man den Subbotovskaya-Hastad-Schrumpfeffekt unter zufälligen Einschränkungen einbeziehen. Ein möglicher Kandidat könnte eine Version der Sipser-Funktion sein, die von Hastad verwendet wird, um zu zeigen, dass Tiefen- ( d + 1 ) -Schaltungen leistungsfähiger sind als jene der Tiefe d .$n^2$$(d+1)$$d$