ACC 0 , a veces llamado ACC , es una clase de modelos y problemas computacionales definidos en complejidad de circuitos , un campo de la informática teórica. La clase se define aumentando la clase AC 0 de "circuitos alternos" de profundidad constante con la capacidad de contar; el acrónimo ACC significa "AC con contadores". [1] Específicamente, un problema pertenece a ACC 0 si puede resolverse mediante circuitos de tamaño polinomial y profundidad constante de puertas de entrada ilimitadas, incluidas puertas que cuentan módulo como un entero fijo. ACC 0 corresponde al cálculo en cualquier monoide soluble . Esta clase se estudia muy bien en informática teórica debido a las conexiones algebraicas y porque es uno de los modelos computacionales concretos más grandes en los que se pueden demostrar resultados de imposibilidad computacional, los llamados límites inferiores del circuito.
De manera informal, ACC 0 modela la clase de cálculos realizados por circuitos booleanos de profundidad constante y tamaño polinómico, donde las puertas del circuito incluyen "puertas de conteo modulares" que calculan el número de entradas verdaderas módulo de una constante fija.
Más formalmente, un lenguaje pertenece a AC 0 [ m ] si puede ser calculado por una familia de circuitos C 1 , C 2 , ..., donde C n toma n entradas, la profundidad de cada circuito es constante, el tamaño de C n es una función polinómica de n , y el circuito utiliza las siguientes puertas: puertas AND y puertas OR de entrada en abanico ilimitada , calculando la conjunción y disyunción de sus entradas; NO puertas que calculan la negación de su entrada única; y puertas MOD- m de entrada en abanico ilimitadas , que calculan 1 si el número de 1 de entrada es múltiplo de m . Un idioma pertenece a ACC 0 si pertenece a AC 0 [ m ] durante algún m .
En algunos textos, ACC i se refiere a una jerarquía de clases de circuitos con ACC 0 en su nivel más bajo, donde los circuitos en ACC i tienen profundidad O (log in ) y tamaño polinómico. [1]
La clase ACC 0 también se puede definir en términos de cálculos de autómatas finitos deterministas no uniformes (NUDFA) sobre monoides . En este marco, la entrada se interpreta como elementos de un monoide fijo y la entrada se acepta si el producto de los elementos de entrada pertenece a una lista determinada de elementos monoide. La clase ACC 0 es la familia de lenguajes aceptados por un NUDFA sobre algún monoide que no contiene un grupo irresoluble como subsemigrupo. [2]
La clase ACC 0 incluye AC 0 . Esta inclusión es estricta, porque una sola puerta MOD-2 calcula la función de paridad, que se sabe que es imposible de calcular en AC 0 . De manera más general, la función MOD m no se puede calcular en AC 0 [ p ] para p primo a menos que m sea una potencia de p . [3]
La clase ACC 0 está incluida en TC 0 . Se conjetura que ACC 0 no puede calcular la función mayoritaria de sus entradas (es decir, la inclusión en TC 0 es estricta), pero esto sigue sin resolverse en julio de 2018.
Cada problema en ACC 0 puede resolverse mediante circuitos de profundidad 2, con puertas AND de fan-in polilogarítmica en las entradas, conectadas a una sola puerta que calcula alguna función simétrica (que no depende del orden de las entradas). [4] Estos circuitos se denominan circuitos SYM + . La prueba sigue ideas de la prueba del teorema de Toda .
Williams (2011) demuestra que ACC 0 no contiene NEXPTIME . La prueba utiliza muchos resultados en la teoría de la complejidad, incluido el teorema de la jerarquía del tiempo , IP = PSPACE , la desrandomización y la representación de ACC 0 a través de circuitos SYM + . [5] Murray & Williams (2018) mejora este límite y demuestra que ACC 0 no contiene NQP (tiempo cuasipolinomial no determinista).
Se sabe que calcular el permanente es imposible para circuitos LOGTIME -uniform ACC 0 , lo que implica que la clase de complejidad PP no está contenida en LOGTIME-uniform ACC 0 . [6]