ACC 0 , a veces llamado ACC , es una clase de modelos y problemas computacionales definidos en la complejidad del circuito , 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 se puede resolver mediante circuitos de profundidad constante y tamaño polinomial de compuertas de entrada en abanico ilimitadas, incluidas las compuertas que cuentan módulo un entero fijo. ACC 0 corresponde al cálculo en cualquier monoide solucionable. La clase está muy bien estudiada en 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.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/7/79/Diagram_of_an_ACC0_Circuit.svg/220px-Diagram_of_an_ACC0_Circuit.svg.png)
Definiciones
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 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 polinomial de n , y el circuito usa las siguientes puertas: puertas Y y puertas O de abanico ilimitado , calculando la conjunción y disyunción de sus entradas; NO compuertas que calculan la negación de su entrada única; y compuertas MOD- m de entrada de abanico ilimitadas , que calculan 1 si el número de entradas 1 es un múltiplo de m . Una lengua pertenece a ACC 0 si pertenece a AC 0 [ m ] durante algunos 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 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 dada de elementos monoide. La clase ACC 0 es la familia de lenguajes aceptados por una NUDFA sobre algún monoide que no contiene un grupo irresoluble como subsemigrrupo. [2]
Potencia de cálculo
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 el primo p 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 abanico polilogarítmico en las entradas, conectadas a una única puerta que calcula una función simétrica. [4] Estos circuitos se denominan circuitos SYM + . La demostración sigue las ideas de la demostración del teorema de Toda .
Williams (2011) demuestra que ACC 0 no contiene NEXPTIME . La demostración utiliza muchos resultados en la teoría de la complejidad, incluido el teorema de la jerarquía de tiempo , IP = PSPACE , desaleatorización y la representación de ACC 0 a través de circuitos SYM + . [5]
Se sabe que calcular el permanente es imposible para los circuitos LOGTIME -uniforme ACC 0 , lo que implica que la clase de complejidad PP no está contenida en LOGTIME-ACC 0 uniforme . [6]
Notas
Referencias
- Allender, Eric (1996), "La complejidad del circuito antes del amanecer del nuevo milenio", 16ª Conferencia sobre los fundamentos de la tecnología del software y la informática teórica, Hyderabad, India, 18-20 de diciembre de 1996 (PDF) , Lecture Notes in Computer Science , 1180 , Springer, págs. 1-18, doi : 10.1007 / 3-540-62034-6_33
- Allender, Eric ; Gore, Vivec (1994), "Un límite inferior de circuito uniforme para lo permanente" (PDF) , SIAM Journal on Computing , 23 (5): 1026–1049, doi : 10.1137 / S0097539792233907
- Barrington, DA (1989), "Los programas de ramificación de tamaño polinómico de ancho acotado reconocen exactamente esos lenguajes en NC 1 " (PDF) , Journal of Computer and System Sciences , 38 (1): 150-164, doi : 10.1016 / 0022- 0000 (89) 90037-8.
- Barrington, David A. Mix (1992), "Algunos problemas que involucran polinomios de Razborov-Smolensky", en Paterson, MS (ed.), Complejidad de la función booleana, Sel. Papilla. Symp., Durham / Reino Unido 1990. , London Mathematical Society Lecture Notes Series, 169 , págs. 109-128, ISBN 0-521-40826-1, Zbl 0769.68041.
- Barrington, DA; Thérien, D. (1988), "Finite monoids and the fine structure of NC 1 ", Journal of the ACM , 35 (4): 941–952, doi : 10.1145 / 48014.63138
- Beigel, Richard; Tarui, Jun (1994), "On ACC", Computational Complexity , 4 (4): 350–366, doi : 10.1007 / BF01263423.
- Clote, Peter; Kranakis, Evangelos (2002), Funciones booleanas y modelos de computación , Textos en Informática Teórica. Una serie EATCS, Berlín: Springer-Verlag , ISBN 3-540-59436-1, Zbl 1016.94046
- Razborov, AA (1987), "Límites inferiores para el tamaño de los circuitos de profundidad acotada con base {⊕, ∨}", Math. Notas de la Academia de Ciencias de la URSS , 41 (4): 333–338.
- Smolensky, R. (1987), "Métodos algebraicos en la teoría de límites inferiores para la complejidad del circuito booleano", Proc. XIX Simposio ACM sobre Teoría de la Computación , págs. 77–82, doi : 10.1145 / 28395.28404.
- Thérien, D. (1981), "Clasificación de monoides finitos: el enfoque del lenguaje", Informática teórica , 14 (2): 195-208, doi : 10.1016 / 0304-3975 (81) 90057-8.
- Vollmer, Heribert (1999), Introducción a la complejidad del circuito , Berlín: Springer, ISBN 3-540-64310-9.
- Williams, Ryan (2011), "Límites inferiores del circuito ACC no uniforme" (PDF) , Conferencia IEEE sobre complejidad computacional : 115-125, doi : 10.1109 / CCC.2011.36 , ISBN 978-1-4577-0179-5.