# ACC0

ACC$^0$, às vezes chamado de ACC, é uma classe de modelos computacionais e problemas definidos em complexidade do circuito, uma área da teoria da computação. A classe é definida aumentando a classe AC$^0$ de "circuitos alternados" de profundidade constante com a capacidade de contar; a sigla ACC significa "AC com contadores" Especificamente, um problema pertence a ACC$^0$ se ele pode ser resolvido por circuitos de profundidade constante com portas lógicas de entrada ilimitadas, de tamanho polinomial, incluindo portas que calculam o MOD de um inteiro fixado. ACC$^0$ corresponde a computação em qualquer monóide solúvel. A classe é muito bem estudada em teoria da computação por causa das conexões algébricas e porque é um dos maiores modelos computacionais concretos para os quais resultados computacionais de impossbilidade, os chamados limitantes inferiores de circuitos, podem ser provados.

## Definições

Informalmente, ACC$^0$ modela a classe de cálculos realizados por circuitos booleanos de profundidade constante e tamanho polinomial, onde as portas do circuito incluem "portas de contagem modular" que calculam o resto da divisão entre o número de entradas verdadeiras por alguma constante fixa.
Mais formalmente, uma linguagem pertence a AC$^0$ [m] se pode ser computada por uma família de circuitos C$_1$, C$_2$, ..., onde C$_n$ possui n entradas, a profundidade de todos os circuitos é constante, o tamanho de C$_n$ é uma função polinomial da variável n, e o circuito utiliza as seguintes portas: portas lógicas AND e portas lógicas OR com fator de carga de entrada irrestrita, calculando a conjunção e a disjunção das suas entradas; Porta lógica NOT computa a negação de sua única entrada; e fator de carga de entrada ilimitada em portas lógicas MOD-m, que computam 1 se o número de 1s na entrada é um múltiplo de m. Uma linguagem pertence a ACC$^0$, se ele pertence a AC$^0$[m] para algum m.
Em alguns textos, ACC$^i$ refere-se a uma hierarquia de classes de circuito com ACC$^0$, em seu nível mais baixo, onde os circuitos em ACC$^i$ tem profundidade O(log$^i$n) e tamanho polinomial.
A classe ACC$^0$ também pode ser definida em termos da computação de autômatos finitos determinísticos não-uniformes (AFDNU) sobre monóides. Nessa abordagem, a entrada é interpretada como elementos de uma monóide fixa, e a entrada é aceita se o produto dos elementos de entrada pertencerem a uma determinada lista de elementos da monóide. A classe ACC$^0$ é a família das linguagens aceitas por um AFDNU sobre alguns monóides que não contém grupos insolúveis como um subsemigrupo.

## Poder computacional

A classe ACC$^0$ inclui AC$^0$. Esta inclusão é rigorosa, porque uma única porta MOD-2 calcula a função de paridade, que é conhecido por ser impossível de calcular em AC$^0$. De modo mais geral, a função MOD$_m$ não pode ser calculada em AC$^0$[p] para p primo, a menos que m seja uma potência de p.
A classe ACC$^0$ está incluída em TC$^0$. Conjectura-se que ACC$^0$ é incapaz de computar a função majoritária de suas entradas (ou seja, a inclusão em TC$^0$ é rigorosa), mas isso continua sem solução desde Julho de 2014.
Todo problema em ACC$^0$ pode ser resolvido por circuitos de profundidade 2, com portas lógicas AND com fator de carga de entrada polilogaritmico nas entradas, ligado a uma única porta computando uma função simétrica. Esses circuitos são chamados circuitos SYM$^+$. A prova segue idéias da prova do teorema de Toda.
Williams (2011) prova que ACC$^0$ não contém NEXPTIME. A prova utiliza muitos resultados em teoria da complexidade, incluindo o teorema da hierarquia de tempo, IP = PSPACE, derandomization, e a representação da ACC$^0$ via circuitos SYM$^+$.
Sabe-se que o cálculo do permanente é impossível para circuitos ACC$^0$ de tempo logaritmico uniforme, o que implica que a classe de complexidade PP não está contida em ACC$^0$ em tempo logaritmico uniforme.