AC (complessità)

Nella complessità dei circuiti, AC è una gerarchia di classi di complessità. Ciascuna classe, ACⁱ, consiste dei linguaggi riconosciuti dai circuiti booleani con profondità ${\displaystyle O(\log ^{i}n)}$ e un numero polinomiale di porte AND e OR, con un numero massimo di linee d'ingresso (fan-in) illimitato.

Il nome "AC" fu scelto per analogia con NC, con la "A" nel nome che sta per "alternante" e si riferisce sia all'alternanza tra le porte AND e OR nei circuiti sia alle macchine di Turing alternanti.^[1]

La classe AC è AC⁰, che consiste di circuiti con numero massimo di linee d'ingresso illimitato a profondità costante.

La gerarchia totale delle classi AC è definita come

${\displaystyle {\mbox{AC}}=\bigcup _{i\geq 0}{\mbox{AC}}^{i}}$

Relazione con NC

Le classi AC sono legate alle classi NC, che sono definite in modo simile, ma con porte che hanno soltanto un numero massimo di linee d'ingresso costante. Per ciascuna i, abbiamo^[2][3]

${\displaystyle {\mbox{NC}}^{i}\subseteq {\mbox{AC}}^{i}\subseteq {\mbox{NC}}^{i+1}.}$

Come conseguenza immediata di questo, abbiamo che NC = AC.^[4]

Si sa che l'inclusione è rigida per i = 0.^[3]

Variazioni

La potenza delle classi AC può essere influenzata aggiungendo porte addizionali. Se aggiungiamo porte che calcolano l'operazione modulo per qualche modulo m, abbiamo le classi ACCⁱ[m].^[4]