ACC 0

ACC ⁰ , 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 ⁰ de "circuitos alternantes" de profundidad constante con la capacidad de contar; el acrónimo ACC significa "AC con contadores". ^{[ 1 ]} Específicamente, un problema pertenece a ACC ⁰ si puede resolverse mediante circuitos de tamaño polinomial y profundidad constante de puertas de entrada ilimitadas, incluidas puertas que cuentan módulo un entero fijo. ACC ⁰ corresponde a la computación en cualquier monoide resoluble . 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 de circuitos.

De manera informal, ACC ⁰ modela la clase de cálculos realizados por circuitos booleanos de profundidad constante y tamaño polinomial, donde las compuertas del circuito incluyen "compuertas de conteo modular" que calculan el número de entradas verdaderas módulo alguna constante fija.

Más formalmente, un lenguaje pertenece a AC ⁰ [ m ] si puede ser calculado por una familia de circuitos C ₁ , C ₂ , ..., 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 fan-in ilimitado , que calculan la conjunción y la 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 1 de entrada es un múltiplo de m . Un lenguaje pertenece a ACC ⁰ si pertenece a AC ⁰ [ m ] para algún m .

En algunos textos, ACC ⁱ se refiere a una jerarquía de clases de circuitos con ACC ⁰ en su nivel más bajo, donde los circuitos en ACC ⁱ tienen profundidad O (log ⁱ n ) y tamaño polinomial. ^{[ 1 ]}

La clase ACC ⁰ 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 se acepta si el producto de los elementos de entrada pertenece a una lista dada de elementos del monoide. La clase ACC ⁰ 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 ⁰ incluye AC ⁰ . 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 ⁰ . De manera más general, la función MOD _m no se puede calcular en AC ⁰ [ p ] para un primo p a menos que m sea una potencia de p . ^{[ 3 ]}

La clase ACC ⁰ está incluida en TC ^0. Se conjetura que ACC ⁰ no puede calcular la función de mayoría de sus entradas (es decir, la inclusión en TC ⁰ es estricta), pero esto sigue sin resolverse a julio de 2018.

Cada problema en ACC ⁰ puede resolverse mediante circuitos de profundidad 2, con compuertas AND de entrada polilogarítmica en las entradas, conectadas a una única compuerta que calcula alguna función simétrica (que no depende del orden de las entradas). ^{[ 4 ]} Estos circuitos se denominan circuitos SYM ⁺ . La demostración sigue ideas de la demostración del teorema de Toda .

Williams (2011) demuestra que ACC ⁰ no contiene NEXPTIME . La demostración utiliza muchos resultados de la teoría de la complejidad, incluyendo el teorema de jerarquía temporal , IP = PSPACE , la desaleatorización y la representación de ACC ⁰ mediante circuitos SYM ^{+ . [ 5 ]} Murray y Williams (2018) mejoran esta cota y demuestran que ACC ⁰ no contiene NQP (tiempo cuasipolinomial no determinista).

Se sabe que el cálculo del permanente es imposible para los circuitos LOGTIME -uniform ACC ⁰ , lo que implica que la clase de complejidad ^PP no está contenida en LOGTIME-uniform ACC ^{0. [ 6} ]