Referencias sobre los límites inferiores del circuito

21

Preámbulo

Goldwasser, Micali y Rackoff y Babai introdujeron sistemas de prueba interactivos y protocolos Arthur-Merlin en 1985. Al principio, se pensó que el primero es más poderoso que el segundo, pero Goldwasser y Sipser demostraron que tienen el mismo poder ( con respecto al reconocimiento del idioma). Por lo tanto, en esta publicación, usaré los dos conceptos indistintamente.

Deje que sea ​​la clase de idiomas que admite un sistema de prueba interactivo con rondas. Babai demostró quek I P [ O ( 1 ) ] Π P 2yoPAGS[k]kyoPAGS[O(1)]Π2PAGS . (Un resultado relativizable).

Al principio, no se sabía si un número ilimitado de rondas puede aumentar el poder de IP. En particular, se ha demostrado tener relativizaciones contradictorias: Fortnow y Sipser mostraron que para algunos oráculo , se cumple que . (Por lo tanto, en relación con A , IP [poli] no es una superclase de PH ).c o N P AI P [ p o l y ] A A I P [ p o l y ] P HUNAdoonortePAGSUNAyoPAGS[pagsoly]UNAUNAyoPAGS[pagsoly]PAGSH

Por otro lado, el siguiente documento:

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

muestra que, por algún oráculo si , tenemos yoPAGS[pagsoly]siPAGSHsi . (Por lo tanto, yoPAGS[pagsoly]siyoPAGS[O(1)]si ya que, como se indicó anteriormente, este último es una subclase de Π2PAGS,si .)


La pregunta

El documento de Aiello, Goldwaseer y Hastad (citado anteriormente) afirma:

Las técnicas empleadas son extensiones de las técnicas para probar los límites inferiores en circuitos de pequeña profundidad utilizados en [FSS], [Y] y [H1].

donde [FSS], [Y] y [H1] son:

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

Los documentos me parecieron muy viejos y extremadamente difíciles de seguir. Leí el capítulo 14 del libro de Arora y Barak , pero aparentemente no cubre todo lo que necesito.

¿Qué referencias en "Circuito Límites inferiores" sugiere?

(Necesito especialmente referencias similares a encuestas; las que son más nuevas y no requieren mucha experiencia son más preferibles).

MS Dousti
fuente
2
Otra referencia más: notas de la conferencia de Avi Wigderson sobre límites inferiores para circuitos monótonos y de profundidad constante (este enlace es del sitio web del borrador de Arora-Barak).
Alessandro Cosentino

Respuestas:

14

UNAdo0 0

Ahora no ha declarado si realmente quiere entender la prueba, o simplemente entender las cosas a un alto nivel, de la manera en que un artículo de la encuesta explicaría las cosas.

Un artículo de la encuesta que leí y me gustó recientemente es " La complejidad de las funciones finitas " de Boppana y Sipser.

Si realmente quiere sentarse y comprender la prueba, puede leer las pruebas basadas en el lema Switching (que aparece en los documentos que citó: [FSS], [Y] y [H1]), o el Razborov-Smolensky prueba.

Para pruebas usando el Lema de conmutación, el Ph.D. de Håstad La tesis es una buena lectura, aunque un poco difícil de seguir si eres nuevo en el área. Una mejor exposición de la prueba se encuentra en "Introducción a la complejidad del circuito y una guía de la prueba de Håstad" de Allan Heydon. El único problema es que no puedo encontrarlo en línea y tengo una copia impresa. Realmente lo recomiendo si eres nuevo en la complejidad del circuito.

Para el enfoque Razborov-Smolensky, solo busque en Google y obtendrá un montón de notas de clase. Comprendí el límite inferior de estas tres notas de conferencia: Sanjeev Arora , Madhu Sudan y Kristo ff er Arnsfelt Hansen .

Robin Kothari
fuente
¿Sugiere alguna forma de obtener una copia de la exposición de Allan Heydon de la prueba?
MS Dousti
@Sadeq: No tengo idea. Lo obtuve de mi biblioteca. Está incluido en la página de informes técnicos de CMU ( cs.cmu.edu/~clamen/reports/1990.html ) como un informe técnico como CMU-CS-90-141, pero no hay un enlace para descargarlo o encontrarlo en línea. Puedes intentar enviar un correo electrónico al autor.
Robin Kothari
1
Finalmente obtuve un enlace al informe técnico de Allan Heydon sobre el repositorio de CMU .
MS Dousti
14

Si encuentra que la exposición de Switching Lemma en la tesis de Hastad es difícil de seguir, puede probar `` A Switching Lemma Primer '' de Paul Beame , que tiene una versión diferente debido a Razborov (que también utiliza explícitamente árboles de decisión, algo que es crucial en algunas aplicaciones del Lema de conmutación)

Srikanth
fuente
14

Este libro es excelente para explicar los límites inferiores, si tiene acceso a él.

Introducción a la complejidad del circuito por Heribert Vollmer.

Acabo de terminar de leerlo, y aunque dice "introducción" es un tratamiento muy profundo sobre la complejidad del circuito. Explica con detalles todas las técnicas (más populares) para probar los límites inferiores del circuito en el capítulo 3.

Marcos Villagra
fuente