AC (complexité)
# AC (complexité)

En théorie de la complexité, AC est la classe de complexité définie comme l'union des $AC^i,$ où $AC^i$ est la classe de complexité des problèmes décidés par des circuits booléens de profondeur $O(\log ^{i}n)$, de taille polynomiale, dont les portes sont des ET et des OU, de degrés entrants non bornés (en fait, d'autres portes peuvent être autorisés comme des portes "OU exclusif" ou NON car elles sont exprimables, sans changer la complexité, par des ET et des OU).

En particulier, $AC^0$ est la classe de complexité des problèmes décidés par des circuits booléens de profondeur constante, de taille polynomiale.

## AC = NC

Les classes NC et $NC^i$ sont analogues à AC et $AC^i$ sauf que l'arité des portes logiques est borné. On a :

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

Ainsi, les classes AC et NC sont égales.

