Paridad y

19

La paridad y son como gemelos inseparables. O eso parece durante los últimos 30 años. A la luz del resultado de Ryan, habrá un renovado interés en las clases pequeñas. $AC^0$

Furst Saxe Sipser a Yao a Hastad son todas paridades y restricciones aleatorias. Razborov / Smolensky es un polinomio aproximado con paridad (ok, puertas mod). Aspnes et al usan un grado débil en la paridad. Además, Allender Hertrampf y Beigel Tarui tratan sobre el uso de Toda para clases pequeñas. Y Razborov / Beame con árboles de decisión. Todos estos caen en la canasta de paridad.

1) ¿Cuáles son otros problemas naturales (aparte de la paridad) que se pueden demostrar directamente que no están en $AC^0$ ?

2) ¿Alguien sabe de un enfoque drásticamente diferente para el límite inferior en AC ^ 0 que se ha probado?

cc.complexity-theory complexity-classes lower-bounds circuit-complexity V Vinay
fuente

13

Resultado de Benjamin Rossman en inferior para k-clique de STOC 2008. $AC^0$

Referencias

Paul Beame, " A Primer cambio de lema ", Informe técnico 1994.
Benjamin Rossman, " Sobre la complejidad de la profundidad constante de k-Clique ", STOC 2008.

Kaveh
fuente

¿No está Rossman subsumido por la cartilla de Beame que también tenía camarilla? Los argumentos son más complejos, por supuesto.

V Vinay

@ V Vinay: ¿puedes dar un enlace al artículo de Paul Beame?

Kaveh

44

El resultado de Rossman muestra que -clique no puede calcularse mediante circuitos de profundidad constante de tamaño . Tenga en cuenta que la constante en el exponente no depende de la profundidad del circuito, que es donde mejora el límite inferior Beame .

k

$k$

Ω (n^{k / 4})

$\Omega(n^{k/4})$

n^{Ω (k / d^{2})}

$n^{\Omega(k/d^2)}$

Srikanth el

@Srikanth, pensé que V Vinay está diciendo que Beame tiene un resultado más nuevo, pero no pude encontrar ninguno en su página. Gracias por la aclaración.

Kaveh

1

Srikanth tiene razón sobre los límites. Kaveh, no es un periódico nuevo; Usé "subsumido" en el sentido de que había incluido a Beame en mi pregunta y, por lo tanto, estaba al tanto del límite inferior de la camarilla.

V Vinay

12

Existe el enfoque "de arriba hacia abajo" de Håstad, Jukna y Pudlák, como se hace en su artículo Límites inferiores de arriba hacia abajo para los circuitos de profundidad tres . Desafortunadamente, hasta ahora no hemos podido extender el enfoque a profundidades más altas.

Kristoffer Arnsfelt Hansen
fuente

Si. ¿Pensé que tenías un artículo influenciado por este enfoque?

V Vinay

10

1) Lo primero que viene a mi mente es MAYORÍA. Puede probar que no está en con las mismas técnicas. Ver la tesis de Håstad para más detalles. $AC^{0}$

2) Kriegel y Waack propusieron un enfoque topológico, de nuevo trabajando solo para circuitos de profundidad tres .

Alessandro Cosentino
fuente

2

La mayoría es lo mismo realmente. Aunque debería haberlo mencionado. Además, hubo un artículo de Boppana sobre Mayoría a mediados de los años 80.

V Vinay

8

Los otros dos métodos "clásicos" son el método de cuello de botella de Haken y el método de fusión de Karchmer (llamado así por Avi Wigderson), ambos mucho más fáciles de aplicar en el entorno monótono.

Yuval Filmus
fuente

Paridad y

Respuestas: