AC (complessità)

Nella complessità dei circuiti, AC è una gerarchia di classi di complessità. Ciascuna classe, AC^i, 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^0, 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^i[m].[4]

Note

1. Regan (1999), pp. 27-18.
2. Clote & Kranakis (2002), p. 437.
3. Arora & Barak (2009), p. 118.
4. Clote & Kranakis, p. 12.

Bibliografia

• 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.