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

$\text{AC}=\bigcup _{i\ge 0}{\text{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:

${\text{NC}}^i\subseteq {\text{AC}}^i\subseteq {\text{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].