ACC 0 , a veces llamado ACC , es una clase de modelos computacionales y problemas 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 polinómico y profundidad constante de puertas fan-in ilimitadas, incluidas las puertas que cuentan módulo un entero fijo. ACC 0 corresponde al cálculo en cualquier monoide resoluble . La clase está muy bien estudiada en la informática teórica debido a las conexiones algebraicas y porque es uno de los modelos computacionales concretos más grandes para 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 polinomial, donde las puertas del circuito incluyen "puertas de conteo modulares" que calculan el número de entradas verdaderas módulo alguna constante fija.
Más formalmente, un lenguaje pertenece a AC 0 [ m ] si puede ser computado 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 usa las siguientes puertas: puertas AND y puertas OR de fan-in ilimitado , que calculan la conjunción y disyunción de sus entradas; puertas NOT que calculan la negación de su única entrada; y puertas MOD- m de fan-in ilimitado , que calculan 1 si el número de entradas 1 es un múltiplo de m . Un lenguaje pertenece a ACC 0 si pertenece a AC 0 [ m ] para 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 i n ) y tamaño polinomial. [1]
La clase ACC 0 también puede definirse 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 dada de elementos de monoide. La clase ACC 0 es la familia de lenguajes aceptados por un NUDFA sobre algún monoide que no contenga un grupo irresoluble como subsemigrupo. [2]
La clase ACC 0 incluye AC 0 . Esta inclusión es estricta, porque una única puerta MOD-2 calcula la función de paridad, que se sabe que es imposible de calcular en AC 0 . En términos más generales, la función MOD m no se puede calcular en AC 0 [ p ] para el primo p a menos que m sea una potencia de p . [3]
La clase ACC 0 está incluida en TC 0. Se supone 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 a julio de 2018.
Todo problema en ACC 0 puede resolverse mediante circuitos de profundidad 2, con puertas AND de abanico de entrada polilogarítmico en las entradas, conectadas a una única 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 las ideas de la prueba del teorema de Toda .
Williams (2011) demuestra que ACC 0 no contiene NEXPTIME . La prueba utiliza muchos resultados de la teoría de la complejidad, incluido el teorema de la jerarquía temporal , IP = PSPACE , la desaleatorización y la representación de ACC 0 mediante circuitos SYM + . [5] Murray y Williams (2018) mejoran este límite y demuestran que ACC 0 no contiene NQP (tiempo cuasipolinomial no determinista).
Se sabe que calcular la permanente es imposible para circuitos ACC 0 uniformes LOGTIME , lo que implica que la clase de complejidad PP no está contenida en ACC 0 uniformes LOGTIME . [6]