¿Por qué son interesantes las puertas mod

39

Ryan Williams acaba de publicar su límite inferior en ACC , la clase de problemas que tienen circuitos de profundidad constante con ventiladores y puertas ilimitadas AND, OR, NOT y MOD_m para todos los m posibles.

¿Qué tienen de especial las puertas MOD_m?

Permiten simular aritmética sobre cualquier anillo Z_m.
Antes del resultado de Ryan, arrojar puertas MOD_m a la mezcla dio la primera clase para la cual los límites inferiores conocidos no funcionaban.

¿Hay alguna otra razón natural para estudiar las puertas MOD_m?

cc.complexity-theory circuit-complexity big-picture circuit-families Dana Moshkovitz
fuente

39

$ACC^0$ es una clase de complejidad natural.

1) Barrington demostró que el cálculo sobre los monoides no solubles capturan mientras que sobre los monoides solubles capturan . $NC^1$ $ACC^0$

2) Recientemente, Hansen y Koucky demostraron un resultado hermoso de que los programas de ramificación plana de ancho constante de tamaño polivinílico son exactamente . Sin la condición de planaridad, por supuesto obtenemos el resultado de Barrington que caracteriza a . $ACC^0$ $NC^1$

Entonces, la diferencia entre y es teórica de grupo por un lado y topológica por el otro. $ACC^0$ $NC^1$

Agregado: Dana, un ejemplo simple de un grupo solucionable es , el grupo simétrico sobre elementos. Sin entrar en detalles, cualquier grupo solucionable tiene una serie cuyos cocientes resultan ser cíclicos. Esta estructura cíclica se refleja como puertas modificadas al construir un circuito para resolver problemas de palabras en el grupo. $S_4$

Sobre la planaridad, a uno le gustaría creer que la planaridad puede imponer restricciones / cuellos de botella en el flujo de información. Esto no siempre es cierto: por ejemplo, se sabe que las variaciones de 3SAT planas son NP completas. Sin embargo, en clases más pequeñas, es más probable que estas restricciones se cumplan.

De manera similar, Wigderson mostró NL / poly = UL / poly usando el lema de aislamiento. No sabemos cómo desrandomizar el lema de aislamiento sobre DAG arbitrarios para obtener NL = UL, pero sabemos cómo hacerlo para DAG planos.

V Vinay
fuente

1

¡Muchas gracias por la información! Me encantaría saber más sobre la intuición de estos resultados. En cuanto a mi pregunta: su argumento es básicamente que [O (log n) profundidad, puertas AND, OR, NOT] es natural, y es una ligera variación de la misma (a monoides solubles en lugar de no solubles, o a programas de ramificación planos en lugar de no planos). ¿Podría elaborar un poco: dar ejemplos de monoides interesantes para el cálculo y cómo importa su capacidad de solución? ¿Existe una motivación a priori para interesarse en si un programa de ramificación es plano o no?

N C^{1}

$NC^1$

A C C

$ACC$

Dana Moshkovitz el

77

Para complementar: 1) Computación sobre monoides aperiódicos captura (Barrington y Thérien). 2) Los programas de ramificación planar hacia arriba capturan (Barrington, Lu, Miltersen, Skyum).

A C^{0}

$AC^0$

A C^{0}

$AC^0$

Kristoffer Arnsfelt Hansen

@Vinay: ¿Estás seguro de que el resultado NL / poly = UL / poly se debe a Wigderson?

Dai Le

17

$\bmod m$ $m$ $\bmod p$

Considere la clase de circuitos de constantes de profundidad que consisten solamente de puertas, y entradas y constantes en las hojas. Entonces, uno puede mostrar fácilmente que la función OR (por ejemplo) no puede ser calculada por dichos circuitos, independientemente del tamaño del circuito. (Esto se debe a que cualquiera de estos circuitos calcula un polinomio de bajo grado sobre , y el grado de OR es ). $\bmod p$ $\mathbb{F}_p$ $n$

Sin embargo, si consideramos los circuitos que consisten solo en compuertas donde tiene al menos dos factores primos distintos, hay un circuito de profundidad (de tamaño exponencial) para la función OR. $\bmod m$ $m$ $2$

Y antes del resultado de Ryan, fue, supongo, la clase más pequeña para la que no teníamos límites inferiores decentes. $AC^0[\bmod 6]$

Ramprasad
fuente

1

Anexo a la última oración: Ya se sabía que calcular con circuitos de profundidad constante utilizando las puertas AND, OR, NOT y para los primos requería un número exponencial de puertas. (También hay una extensión para los compuestos relativamente primos). Dado que 6 es el compuesto más pequeño de dos primos distintos, es la función "más fácil" para calcular que no se conocía ningún límite inferior exponencial.

M O D_{q}

$MOD_q$

M O D_{p}

$MOD_p$

p \neq q

$p \ne q$

M O D_{6}

$MOD_6$

Daniel Apon

14

Solo para elaborar sus dos puntos:

Si estamos en el negocio de entender la computación, el conteo modular es una de las fronteras de nuestra comprensión. El conteo modular es uno de los fenómenos más simples y naturales en la computación, sin embargo, parece que entendemos muy poco al respecto. No podemos descartar la posibilidad de que los circuitos de profundidad polinómica de tamaño 3 con solo compuertas Mod6 puedan calcular todas las funciones en NP. Sin embargo, se conjetura que tales circuitos solo pueden calcular funciones con un gran tamaño de soporte y, por lo tanto, no pueden calcular una función muy simple como AND. En el lado del límite superior, la situación es similar, no tenemos resultados no triviales.

Estas preguntas también son muy interesantes desde una perspectiva puramente matemática, ya que están estrechamente relacionadas con preguntas muy naturales sobre polinomios y matrices sobre Z_m. Para dar un ejemplo, no tenemos buenos límites inferiores para el rango de una matriz codiagonal nxn sobre Z_6. Una matriz codiagonal tiene 0s en diagonal y nonzeros fuera de diagonal.

aada
fuente

Aquellos interesados en el "módulo principal versus compuesto" deben consultar la página de inicio de Vince Grolmusz: grolmusz.pitgroup.org

Stasys

¿Por qué son interesantes las puertas mod_m?

Respuestas: