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}}$

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]

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]

• Sanjeev Arora e Boaz Barak, Computational complexity. A modern approach, Cambridge University Press, 2009, ISBN 978-0-521-42426-4, Zbl 1193.68112.
• Peter Clote e Evangelos Kranakis, Boolean functions and computation models, Texts in Theoretical Computer Science. An EATCS Series, Berlino, Springer-Verlag, 2002, ISBN 3-540-59436-1, Zbl 1016.94046.
• Kenneth W. Regan, Complexity classes, in Algorithms and Theory of Computation Handbook, CRC Press, 1999.
• Heribert Vollmer, Introduction to circuit complexity. A uniform approach, Texts in Theoretical Computer Science, Berlino, Springer-Verlag, 1998, ISBN 3-540-64310-9, Zbl 0931.68055.

Portale Informatica

Portale Matematica