Références sur les limites inférieures du circuit

Préambule

Les systèmes de preuve interactifs et les protocoles Arthur-Merlin ont été introduits par Goldwasser, Micali et Rackoff et Babai en 1985. Au début, on pensait que le premier était plus puissant que le second, mais Goldwasser et Sipser ont montré qu'ils avaient le même pouvoir ( en ce qui concerne la reconnaissance de la langue). Par conséquent, dans ce post, je vais utiliser les deux concepts de manière interchangeable.

Soit la classe de langages admettant un système de preuve interactif à tours. Babai prouvé que . (Un résultat relativisable.)$IP[k]$$k$$IP[O(1)] \subseteq \Pi_2^P$

Au début, on ne savait pas si un nombre illimité de tours pouvait augmenter la puissance de l'IP. En particulier, il a été démontré que relativisations contradictoires: Fortnow et Sipser ont montré que , pour un oracle , il estime que . (Par conséquent, par rapport à A , IP [poly] n'est pas une superclasse de PH .)$A$$coNP^A \not\subset IP[poly]^A$$A$$IP[poly]$$PH$

D'autre part, le papier suivant:

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

montre que, pour un oracle $B$ , nous avons $IP[poly]^B \not\subset PH^B$ . (Par conséquent, $IP[poly]^B \neq IP[O(1)]^B$ puisque, comme indiqué ci-dessus, cette dernière est une sous-classe de $\Pi_2^{P,B}$ .)

La question

L'article d'Aiello, Goldwaseer et Hastad (cité ci-dessus) déclare:

Les techniques utilisées sont des extensions des techniques de vérification des bornes inférieures sur les circuits de faible profondeur utilisés dans [FSS], [Y] et [H1].

où [FSS], [Y] et [H1] sont:

[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.

J'ai trouvé les papiers très anciens et extrêmement difficiles à suivre. J'ai lu le chapitre 14 du livre d' Arora & Barak , mais apparemment, il ne couvre pas tout ce dont j'ai besoin.

Quelles références sur "Circuit Lower Bounds" proposez-vous?

(J'ai particulièrement besoin de références de type enquête; celles qui sont plus récentes et qui n'ont pas besoin de beaucoup d'expertise sont plus préférables.)

Ce que vous voulez, c'est une bonne référence pour comprendre les limites inférieures exponentielles des circuits calculant la fonction PARITY.$AC^0$

Maintenant, vous n'avez pas indiqué si vous voulez réellement comprendre la preuve, ou simplement comprendre les choses à un niveau élevé, la façon dont un article d'enquête expliquerait les choses.

Un article d’enquête que j’ai récemment lu et aimé est « La complexité des fonctions finies » de Boppana et Sipser.

Si vous voulez vraiment vous asseoir et comprendre la preuve, vous pouvez soit lire les preuves basées sur le lemme de commutation (qui apparaissent dans les articles que vous avez cités - [FSS], [Y] et [H1]), ou le Razborov-Smolensky preuve.

Pour les preuves utilisant le Switching Lemma, le Ph.D. de Håstad la thèse est une bonne lecture, mais un peu difficile à suivre si vous êtes nouveau dans la région. Une meilleure exposition de la preuve est dans "Introduction à la complexité du circuit et un guide pour la preuve de Håstad" par Allan Heydon. Le seul problème, c'est que je ne le trouve pas en ligne et j'ai une copie papier. Je le recommande vraiment si vous êtes nouveau dans la complexité des circuits.

Pour l'approche Razborov-Smolensky, recherchez simplement Google et vous obtiendrez un tas de notes de cours. J'ai compris la limite inférieure de ces trois notes de cours: Sanjeev Arora , Madhu Sudan et Kristo ff er Arnsfelt Hansen .

Si vous trouvez que l'exposition du Switching Lemma dans la thèse de Hastad est difficile à suivre, vous pouvez essayer `` A Switching Lemma Primer '' de Paul Beame , qui a une version différente en raison de Razborov (qui utilise également explicitement des arbres de décision, ce qui est crucial) dans certaines applications du lemme de commutation)

Ce livre est idéal pour expliquer les limites inférieures, si vous y avez accès.

Introduction à la complexité des circuits par Heribert Vollmer.

Je viens juste de le lire, et même s'il dit "introduction", c'est un traitement très approfondi de la complexité du circuit. Il explique en détail toutes les techniques (les plus populaires) pour prouver les limites inférieures du circuit dans le chapitre 3.

Une référence plus récente serait la complexité de la fonction booléenne par Stasys Jukna. Il vous suffit de lui envoyer un e-mail ou de remplir le formulaire pour obtenir le pdf du brouillon.

L' enquête The Complexity of Finite Functions de Boppana et Sipser est une référence plus ancienne mais toujours agréable . Cette enquête est très lisible par rapport à d'autres sources.

Une autre bonne référence est le livre Boolean Functions and Computation Models de Clote et Kranakis.

Je ne suis pas un spécialiste, mais il y a probablement des informations intéressantes dans le livre bleu ( http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ ).

Il y a aussi un article d'Allender en 1997: Circuit Complexity before the Dawn of the New Millennium

Emanuele Viola a publié le livre " On the Power of Small-Depth Computation " qui comprend de nombreux résultats sur les bornes inférieures du circuit.

Une version préliminaire du livre peut être trouvée ici .