AC (complexité)

En théorie de la complexité, AC est la classe de complexité définie comme l'union des ACⁱ, où ACⁱ 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⁰ 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ⁱ sont analogues à AC et ACⁱ 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.

Liens externes

(en) La classe AC sur le Complexity Zoo