ACC0
# 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^in)$ 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.

