AC

Nella complessità dei circuiti, AC è una gerarchia di classi di complessità. Ciascuna classe, ACi, consiste dei linguaggi riconosciuti dai circuiti booleani con profondità 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 . La classe AC è AC0, che consiste di circuiti con numero massimo di linee d'ingresso illimitato a profondità costante. La gerarchia totale delle classi AC è definita come