AC (Complexitat)

En teoria de la complexitat, AC és una jerarquia de classes de complexitat. Cada classe ACⁱ consisteix en els llenguatges reconeguts per un circuit booleà de profunditat $O(\log ^{i}n)$i un nombre polinòmic de portes AND, OR i NOT de fan-in il·limitat.

El nom AC es va triar per analogia al de la classe NC, amb la A referint-se a "alternant", referint-se a les portes AND i OR organitzades de manera alternativa i a les màquines de Turing alternants.

La classe més petita és AC⁰ ,consistent en els circuits de profunditat constant i fan-in il·limitat.

Tota la jerarquia de les classes AC es defineix com

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

Relació amb NC

Les classes AC estan relacionades amb les classes NC, que es defineixen de manera similar però les portes tenen un fan-in fitat i constant. Per cada i, es te:

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

I com a conseqüència immediata d'això, es te que NC = AC.

Se sap que la inclusió és estricta quan i = 0.

Variacions

La capacitat de les classes AC es poden canviar afegint portes addicionals. Si s'afegeixen portes que calculen l'operació mòdul per alguns m, es tenen les classes ACCⁱ[m].