ACC0

Esboço de um circuito ACC: Para um número fixo m, o circuito consiste das portas lógicas NOT, AND, OR, e (Mod m). A entrada de cada porta lógica é delimitada por um polinômio e a profundidade do circuito é delimitada por uma constante.

ACC⁰, às vezes chamado de ACC, é uma classe de modelos computacionais e problemas definidos em complexidade do circuito, uma área teórica de ciência da computação. A classe é definida por aumentar a classe AC⁰ de "circuitos alternados" de profundidade constante com a capacidade de contar; a sigla ACC significa "AC com contadores" Especificamente, um problema pertence a ACC⁰ se ele pode ser resolvido em tamanho polinomial, circuitos de profundidade constante com portas lógicas de entrada ilimitadas, incluindo portas que calculam o MOD de um inteiro fixado. ACC⁰ corresponde a computação em qualquer monóide solucionável. A classe está muito bem estudada em áreas teóricas da ciência da computação por causa das conexões algébricas e porque é um dos maiores modelos computacionais concretos com resultados computacionais impossíveis, assim chamado circuito limites inferiores, pode ser provado.

---

x-----------------------

== == Definições

Informalmente, ACC⁰ 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⁰ [m] se pode ser calculado por uma família de circuitos C₁, C₂, ..., 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 MOD - m, que computam 1 se o número de 1s na entrada é um múltiplo de m. Uma linguagem pertence a ACC⁰, se ele pertence a AC⁰[m] para algum m.

Em alguns textos, ACCⁱ refere-se a uma hierarquia de classes de circuito com ACC⁰, em seu nível mais baixo, onde os circuitos em ACCⁱ tem profundidade O(logⁱn) e tamanho polinomial.

A classe ACC⁰ 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⁰ é a família das linguagens aceitas por um AFDNU sobre alguns monóides que não contém grupos insolúveis como um subsemigrupo.

A classe ACC⁰ está incluída em TC⁰. Conjectura-se que ACC⁰ é incapaz de computar a função majoritária de suas entradas (ou seja, a inclusão em TC⁰ é rigorosa), mas isso continua sem solução desde Julho de 2014.

Todo problema em ACC⁰ 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⁰ 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⁰ via circuitos SYM⁺.

Sabe-se que o cálculo da permanente é impossível para circuitos ACC⁰ de tempo logaritmico uniforme, o que implica que a classe de complexidade PP não está contida em ACC⁰ em tempo logaritmico uniforme.