Referenzen zu Circuit Lower Bounds

Präambel

Interaktive Beweissysteme und Arthur-Merlin-Protokolle wurden bereits 1985 von Goldwasser, Micali, Rackoff und Babai eingeführt . Zuerst wurde angenommen, dass das erstere leistungsfähiger ist als das letztere, aber Goldwasser und Sipser zeigten, dass sie die gleiche Leistung haben ( in Bezug auf die Spracherkennung). Daher werde ich in diesem Beitrag die beiden Konzepte austauschbar verwenden.

Sei die Klasse von Sprachen, die ein interaktives Beweissystem mit Runden zulassen. Babai bewiesen , dass . (Ein relativierbares Ergebnis.)k I P [ O ( 1 ) ] ⊆ Π P $IP[k]$$k$$IP[O(1)] \subseteq \Pi_2^P$

Zunächst war nicht bekannt, ob eine unbegrenzte Anzahl von Runden die Leistung von IP erhöhen kann. Insbesondere wurde gezeigt, dass es widersprüchliche Relativierungen gibt: Fortnow und Sipser zeigten, dass für ein Orakel die . (Daher bezogen auf , ist nicht eine Superklasse von ) .c o N P A ⊄ I P [ p o l y ] A A I P [ p o l y ] P $A$$coNP^A \not\subset IP[poly]^A$$A$$IP[poly]$$PH$

Auf der anderen Seite das folgende Papier:

Aiello, W., Goldwasser, S., and Hastad, J. 1986. On the power of interaction. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (October 27 - 29, 1986). SFCS. IEEE Computer Society, Washington, DC, 368-379. DOI= http://dx.doi.org/10.1109/SFCS.1986.36

zeigt, dass wir für ein Orakel . (Daher IP [poly] ^ B \ neq IP [O (1)] ^ B, da letztere, wie oben angegeben, eine Unterklasse von \ Pi_2 ^ {P, B} ist .)$B$ I P [ p o l y ] B ≠ I P [ O ( 1 ) ] B Π P , B$IP[poly]^B \not\subset PH^B$$IP[poly]^B \neq IP[O(1)]^B$$\Pi_2^{P,B}$

Die Frage

Das Papier von Aiello, Goldwaseer und Hastad (oben zitiert) besagt:

Die angewendeten Techniken sind Erweiterungen der Techniken zum Nachweis von Untergrenzen für Schaltungen mit geringer Tiefe, die in [FSS], [Y] und [H1] verwendet werden.

wobei [FSS], [Y] und [H1] sind:

[FSS] Furst M., Saxe J. and Sipser M., "Parity, Circuits, and the Polynomial Time Hierarchy," Proceedings 22nd Annual IEEE Symposium on Foundations of Computer Science, 1981, 260-270.

[Y] Yao A. "Separating the Polynomial-Time Hierarchy by Oracles," Proceedings of 6th Annual IEEE Symposium on Foundations of Computer Science, 1985, 1-10.

[H1] Hastad J. "Almost optimal lower bounds for small depth circuits," Proceedings of 18th Annual ACM Symposium on Theory of Computing, 1986, 6-20.

Ich fand die Papiere sehr alt und sehr schwer zu folgen. Ich habe Kapitel 14 von Arora & Baraks Buch gelesen , aber anscheinend enthält es nicht alles, was ich brauche.

Welche Referenzen zu "Circuit Lower Bounds" schlagen Sie vor?

(Ich benötige speziell umfrageähnliche Referenzen; diejenigen, die neuer sind und nicht viel Fachwissen benötigen, sind vorzuziehen.)

Was Sie wollen, ist eine gute Referenz, um die exponentiellen Untergrenzen für Schaltungen zu verstehen, die die PARITY-Funktion berechnen.$AC^0$

Jetzt haben Sie nicht angegeben, ob Sie den Beweis tatsächlich oder nur auf hohem Niveau verstehen möchten, wie es in einem Umfrageartikel erklärt wird.

Ein Artikel, den ich kürzlich gelesen und gemocht habe, ist " Die Komplexität endlicher Funktionen " von Boppana und Sipser.

Wenn Sie sich wirklich hinsetzen und den Beweis verstehen möchten, können Sie entweder Beweise lesen, die auf dem Switching-Lemma (das in den von Ihnen zitierten Artikeln - [FSS], [Y] und [H1] - vorkommt) oder auf dem Razborov-Smolensky Beweis.

Für Beweise mit dem Switching Lemma, Håstad's Ph.D. Diese Arbeit ist eine gute Lektüre, wenn es ein bisschen schwierig ist, sie zu verfolgen, wenn Sie neu in der Gegend sind. Eine bessere Darstellung des Beweises findet sich in "Einführung in die Schaltungskomplexität und eine Anleitung zu Håstad's Beweis" von Allan Heydon. Das einzige Problem dabei ist, dass ich es online nicht finden kann und eine Hardcopy habe. Ich kann es nur empfehlen, wenn Sie mit der Komplexität von Schaltkreisen noch nicht vertraut sind.

Für den Razborov-Smolensky-Ansatz gehen Sie einfach auf Google und Sie erhalten eine Reihe von Vorlesungsskripten. Ich verstand die Untergrenze aus diesen drei Vorlesungsskripten: Sanjeev Arora , Madhu Sudan und Kristo ff er Arnsfelt Hansen .

Wenn Sie die Darstellung des Switching Lemma in Hastads Dissertation als schwierig empfinden, können Sie Paul Beames `` A Switching Lemma Primer '' ausprobieren , der aufgrund von Razborov eine andere Version hat (der auch explizit Entscheidungsbäume verwendet, was von entscheidender Bedeutung ist) in einigen Anwendungen des Switching Lemma)

Dieses Buch eignet sich hervorragend zum Erläutern von Untergrenzen, wenn Sie Zugriff darauf haben.

Einführung in die Schaltungskomplexität von Heribert Vollmer.

Ich habe es gerade gelesen und obwohl es heißt "Einführung" ist eine sehr tiefe Behandlung der Schaltungskomplexität. In Kapitel 3 werden alle (gängigsten) Techniken zum Nachweis von Schaltkreisuntergrenzen ausführlich erläutert.

Eine neuere Referenz wäre Boolean Function Complexity von Stasys Jukna. Sie müssen ihm nur eine E-Mail schreiben oder das Formular ausfüllen, um das PDF des Entwurfs zu erhalten.

Eine ältere, aber immer noch schöne Referenz ist die Umfrage Die Komplexität endlicher Funktionen von Boppana und Sipser. Diese Umfrage ist im Vergleich zu anderen Quellen sehr lesbar.

Eine weitere gute Referenz ist das Buch Boolean Functions and Computation Models von Clote und Kranakis.

Ich bin kein Spezialist, aber es gibt wahrscheinlich interessante Informationen im Blue Book ( http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ ).

Es gibt auch einen Aufsatz von Allender aus dem Jahr 1997: Circuit Complexity before the Dawn of the New Millennium

Emanuele Viola hat das Buch " On the Power of Small-Depth Computation " veröffentlicht, das viele Ergebnisse zu Schaltkreisuntergrenzen enthält.

Eine vorläufige Version des Buches finden Sie hier .