# ACC0

ACC$^0$, a volte chiamata ACC, è una classe di modelli e problemi computazionali definiti nella complessità dei circuiti, un campo dell'informatica teorica. La classe è definita accrescendo la classe AC$^0$ di "circuiti alternanti" a profondità costante con la capacità di contare; l'acronimo ACC sta per "AC con contatori". Specificamente, un problema appartiene ad ACC$^0$ se può essere risolto da circuiti in tempo polinomiale e a profondità costante con porte aventi il numero massimo di linee d'ingresso (fan-in) limitato, incluse porte che contano modulo un intero fisso. ACC$^0$ corrisponde alla computazione in qualsiasi monoide risolvibile. La classe è molto ben studiata in informatica teorica a causa delle connessioni algebriche e perché è uno dei più grandi modelli computazionali concreti per i quali possono essere provati i risultati di impossibilità computazionali, i cosiddetti limiti inferiori dei circuiti.

## Definizioni

Informalmente, ACC$^0$ modella la classe di computazioni realizzate da circuiti booleani di profondità costante e dimensione polinomiale, dove le porte dei circuiti comprendono "porte contatrici modulari" che computano il numero di vere entrate modulo qualche costante fissa.
Più formalmente, un linguaggio appartiene ad AC$^0$[m] se può essere computato da una famiglia di circuiti C$_1$, C$_2$, ..., dove C$_n$ richiede n entrate, la profondità di ogni circuito è costante, la dimensione di C$_n$ è una funzione polinomiale di n, e il circuito usa le porte seguenti: porte AND e porte OR con numero massimo di linee d'ingresso limitato, che computano la congiunzione e la disgiunzione delle entrate; porte NOT che computano la negazione della loro unica entrata; e porte MOD-m con numero massimo di linee d'ingresso illimitato, che computano 1 se il numero di entrata 1s è un multiplo di m. Un linguaggio appartiene ad ACC$^0$ se appartiene ad AC$^0$[m] per un qualche m.
In alcuni testi, ACC$^i$ si riferisce a una gerarchia di classi di circuiti con ACC$^0$ al suo livello più basso, dove i circuiti in ACC$^i$ hanno profondità O(log$^i$n) e dimensione polinomiale.
La classe ACC$^0$ può essere definita anche in termini di computazioni di automi finiti deterministici non uniformi (nonuniform deterministic finite automata, NUDFA) sui monoidi. In questa cornice, l'entrata è interpretata come elementi da un monoide fisso, e l'entrata è accettata se il prodotto degli elementi dell'entrata appartiene a una data lista di elementi del monoide. La classe ACC$^0$ è la famiglia di linguaggi accettati da un NUDFA su qualche monoide che non contiene un gruppo irrisolvibile come sottosemigruppo.

## Potenza computazionale

La classe ACC$^0$ include AC$^0$. Questa inclusione è rigida, perché un'unica porta MOD-2 computa la funzione di parità, che si sa essere impossibile da computare in AC$^0$. Più in generale, la funzione MOD$_m$ non può essere computata in AC$^0$[p] per un numero primo p a meno che m non sia una potenza di p.
Ogni problema in ACC$^0$ può essere risolta da circuiti di profondità 2, con porte AND con numero massimo di linee d'ingresso polilogaritmico alle entrate, connesse a una porta singola che computa una funzione simmetrica. Questi circuiti sono chiamati circuiti SYM$^+$.
La classe ACC$^0$ è inclusa in TC$^0$.
Ryan Williams annunciò nel 2010 e pubblicò nel 2011 una dimostrazione che ACC$^0$ non contiene NEXPTIME. La dimostrazione usa molti risultati nella teoria della complessità, compresi la teoria della gerarchia temporale, IP = PSPACE, la derandomizzazione e le idee nella dimostrazione del teorema di Toda.
Si sa che computare il permanente è impossibile per i circuiti ACC$^0$ uniformi in tempo logaritmico, il che implica che la classe di complessità PP non è contenuta in ACC$^0$ uniforme in tempo logaritmico.
Si congettura che ACC$^0$ sia incapace di computare la funzione di maggioranza delle sue entrate, ma questo quesito era irrisolto al luglio 2012.