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

25

Frage:

Was ist die bekannteste untere Grenze der Formelgröße für eine explizite Funktion in AC 0 ? Gibt es eine explizite Funktion mit einem Ω(n2) 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.Ω(n3o(1))Ω(n2.5o(1))Ω(n2)

Diese beiden Funktionen befinden sich jedoch nicht in AC 0 . Ich frage mich, ob wir eine explizite Funktion in AC 0 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 0 befindet. Daher suche ich nach einer Untergrenze für eine explizite AC 0 -Funktion, die besser ist als Ω ( n 2 / log n ) , vorzugsweise Ω ( n 2 ) .Ω(n2/logn)Ω(n2/logn)Ω(n2)

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.

Robin Kothari
quelle
Kann der Grund für das Fehlen von superlinearen unteren Schranken für -Funktionen eine Art Selbstreduzierbarkeit für A C 0 -Funktionen sein? dh wenn wir eine Untergrenze von n 1 + ϵ haben (wobei ϵ nicht von der Tiefe abhängt), erhalten wir eine Superpoly-Untergrenze. AC0AC0n1+ϵϵ
Kaveh
@Kaveh: Ich bin mir nicht sicher, ob ich das verstehe. Wir haben bereits eine untere Grenze von für eine Funktion in A C 0 (Elementunterscheidbarkeit). Ω(n2/logn)AC0
Robin Kothari
Tut mir leid, ersetze die Superlinearität durch superquadratisch. Ich meine etwas Ähnliches wie Allender-Koucky-Ergebnis für . Der Exponent für A C 0 könnte größer sein. Ein solches Ergebnis kann erklären, warum es schwierig ist, A C 0 -Untergrenzen für A C 0 -Funktionen zu finden. TC0AC0AC0AC0
Kaveh,
Es scheint, dass jedes Problem, das für unter Turing N C 0 -Reduktionen vollständig ist, stark selbstreduzierbar ist, aber dies scheint nicht das zu geben, was ich erwartet habe, da die Größe der Selbstreduktion polynomiell groß sein kann. AC0NC0
Kaveh

Antworten:

15

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 n gebenAC0AC0AC0n2/lognaus informationstheoretischen Gründen. Kann es also sein, dass alles in AC0 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 und2nn×nGV={1,,2n}aijinj>naijsind 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 . GGnϵ Σ3n1/22m=2lognnϵ

Stasys
quelle
Willkommen bei cstheory. :) (Übrigens, Ihr neues Buch sieht ziemlich interessant aus, leider bin ich kein englischer Muttersprachler, also kann ich beim Korrekturlesen nicht anders.)
Kaveh
Tatsächlich sind Kommentare / Kritiker zu den Inhalten / Verweisen usw. an dieser Stelle ebenfalls sehr wichtig. Die aktuelle Version ist hier . Benutzer: Freund Passwort: catchthecat
Stasys
Danke :) Ich werde die letzten Kapitel über die Komplexität von Aussagenbeweisen lesen.
Kaveh
2
Vielen Dank für die Antwort! Wenn Sie an eine Funktion in denken, für die Sie eine Formel mit der Größe Ω ( n 2 ) benötigen , würde mich dies interessieren. AC0Ω(n2)
Robin Kothari
12

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 sindAC0 nkkAC0AC0exp(nk)kexp(tlogn)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 C istn2nF(X)=f(g(X1),,g(Xb))b=logng 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 / 2AC0n/bfbfgkXgg23/2wie 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 / 2F(X)n3/k2AC0 n1/dd2n2AC0n1/2Variablen. 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 / b ab)F(X)n2/lognn/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 nF(X)sXig(Xi)n/bsn/b=n/lognmal die Formelgröße von f , dh s n 2 - o ( 1 )2b/logb=n/loglognfsn2o(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 .n2(d+1)d

Stasys
quelle