Ist es möglich, Zufallsbeschränkungen zu verwenden, um eine Untergrenze für

Es gibt mehrere bekannte -Schaltungsgrößen-Untergrenzen-Ergebnisse, die auf Zufallsbeschränkungen und dem Umschalt-Lemma basieren . $\mathsf{AC^0}$

Können wir ein Switching-Lemma-Ergebnis entwickeln, um eine Größenuntergrenze für -Schaltungen zu beweisen (ähnlich zu den Untergrenzenbeweisen für )? $\mathsf{TC^0}$ $\mathsf{AC^0}$

Oder gibt es ein inhärentes Hindernis bei der Verwendung dieses Ansatzes zum Nachweis von -Untergrenzen? $\mathsf{TC^0}$

Sagen Barriereergebnisse wie Natural Proofs etwas über die Verwendung von Switching Lemma-ähnlichen Techniken zum Nachweis von -Untergrenzen aus? $\mathsf{TC^0}$

cc.complexity-theory circuit-complexity lower-bounds boolean-functions Jeigh
quelle

Kennen Sie den Beweis des Lemmawechsels für

A C^{0}

$\mathsf{AC^0}$

Kaveh

Ich habe das Kapitel mit den unteren Grenzen der Schaltung in Aroras Lehrbuch gelesen. Erstens, transformieren Sie einen Cirtuit mit konstanter Tiefe in einen Schaltkreis ohne NICHT-Gatter mit verschachtelten UND-ODER-Ebenen, und zweitens, wenn Sie den Switching Lemma-Schalter für diese beiden Ebenen verwenden, erhalten Sie schließlich eine Schaltkreisoberseite und die zweite Ebene besteht aus denselben UND- (oder ODER-) Gattern Auf diese Weise können wir dem Schaltkreis eine Schicht entziehen und die Schaltkreistiefe verringern.

Jeigh

Es ist jedoch nicht einfacher als der Boolesche Fall, die Ausgabe eines Gatters zu beobachten, wenn wir mehrere Werte von Eingaben festlegen (im Booleschen Fall legen wir die Quadratwurzel von n Eingaben fest). AND Gate und OR Gate sind extreme Versionen der Threshhold Gates und es ist sehr einfach, den Einfluss von Restriktionen zu beobachten.

Jeigh

Die Idee hinter der Zufallsbeschränkungstechnik ist, dass ein durch eine Zufallsbeschränkung getroffenes

einfacher (tatsächlich konstant) wird, mit einer Wahrscheinlichkeit ungleich Null, während genügend freie Variablen beibehalten werden. Im Gegensatz zu

und

Toren, ein einzelnes

A C^{0}

$\mathsf{AC^0}$

\land

$\land$

\lor

$\lor$

gate, das von einer zufälligen Einschränkung getroffen wird, berechnet immer noch a

\mod p

$\mod p$

Gate auf kleinere Eingänge und wird nicht einfacher.

\mod p

$\mod p$

Kaveh

Beachten Sie auch, dass zufällige Beschränkungen und das Umschalt-Lemma eines der besten Beispiele für natürliche Beweise sind. In jedem Fall wird ein Schaltungsexperte hoffentlich eine umfassendere Antwort veröffentlichen. ps: Ich habe mir die Freiheit genommen, die Frage umzuschreiben. Wenn dir meine Bearbeitung nicht gefällt, kannst du jederzeit einen Rollback durchführen.

Kaveh

Antworten:

Es ist tatsächlich möglich, Zufallsbeschränkungen zu verwenden, um Untergrenzen für Schwellenwertschaltungen zu beweisen.

Insbesondere in der Veröffentlichung Size-Depth Tradeoffs for Threshold Circuits verwenden Impagliazzo, Paturi und Saks Zufallsbeschränkungen, um eine Untergrenze des Superliners (für die Anzahl der Drähte) für Schwellwertschaltungen mit konstanter Tiefe zu beweisen, die die Paritätsfunktion berechnen.

Für den Nachweis von Superpolynom-Untergrenzen für -Schaltungen ist dann ja das Natural-Proof-Konzept von Bedeutung, da es in Konstruktionen von Pseudozufallsfunktionsgeneratoren gibt . $\mathsf{TC}^0$ $\mathsf{TC}^0$

Kristoffer Arnsfelt Hansen
quelle

Siehe auch die jüngste Veröffentlichung von Daniel Kane und Ryan Williams, Super-Linear Gate und Super-Quadratic Wire Lower Bounds für Schaltungen mit Schwellenwerten für Tiefe 2 und Tiefe 3 (STOC 2016).

Ryan beschreibt das Papier wie folgt (die folgende Beschreibung stammt von seiner Homepage):

Wir geben eine explizite Funktion in für die jeder Großteil der linearen Schwellwertschaltungen mit Tiefe zwei (mit unbegrenzten Gewichten) gleichzeitig etwa Gatter und Drähte benötigt. Wir zeigen auch, dass Andreevs Funktion (berechenbar mit einer Tiefendrei-Majoritätsschaltung der Größe ) es erfordert, dass ungefähr dieselbe untere Grenze von Gate und Draht mit linearen Tiefendrei-Schwellenwertschaltungen berechnet wird. Ein wichtiges Werkzeug ist das Littlewood-Offord-Lemma, mit dem wir die Auswirkung zufälliger Beschränkungen auf die Eingänge von Schaltkreisen mit niedrigen Schwellenwerten analysieren. $\mathsf{PP}$ $n^{1.5}$ $n^{2.5}$ $O(n)$

Yuval Filmus
quelle