# AC0

En théorie de la complexité, AC$^0$ est une classe de complexité définie par des circuits booléens de profondeur constante. Elle fait partie de la hiérarchie AC. La classe AC$^0$ contient l'addition, mais pas la fonction parité, la multiplication ou le prédicat de primalité (voir plus bas).

## Définition

La classe AC$^0$ est la classe de complexité des problèmes décidés par des circuits booléens de profondeur constante, 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ées comme des portes "OU exclusif" ou NON car elles sont exprimables, sans changer la complexité, par des ET et des OU). Le sigle AC vient de alternation circuit. Elle fait partie de la hiérarchie AC.

## Exemples

L'addition est dans AC$^0$. Plus précisément, pour tout i, le problème de décision qui prend en entrée 2n bits qui représente deux nombres a et b de n bits et qui calcule le ième bit de la somme de a et b est dans AC$^0$.
Voici une façon de construire un circuit pour calculer le ième bit de la somme de a$_{n-1}$...a$_0$ et b$_{n-1}$...b$_0$. Notons ∧ le "et" logique, ∨ le "ou" logique et ⊕ le ou exclusif. On considère a$_j$ comme une proposition, vraie si le jème bit de a vaut 1, et fausse sinon. De même, b$_j$ comme une proposition, vraie si le jème bit de b vaut 1, et fausse sinon. De même, on note s$_j$ comme une proposition, vraie si le jème bit de s vaut 1, et fausse sinon. On introduit également d'autres propositions :
* r$_j$ est vraie s'il y a une retenue pour le jème bit, fausse sinon ;
* g$_j$ est vraie si une retenue est générée au jème bit, fausse sinon ;
* p$_j$ est vraie si la retenue éventuelle est propagée au jème bit, fausse sinon.
On a :
* g$_j$ = a$_j$ ∧ b$_j$
* p$_j$ = a$_j$ ∨ b$_j$
* r$_j$ = (g$_0$ ∧ p$_1$ ∧ ... ∧ p$_{j-1}$) ∨ (g$_1$ ∧ p$_2$ ∧ ... ∧ p$_{j-1}$) ∨ ... ∨ g$_{j-1}$
* s$_j$ = (a$_j$ ⊕ b$_j$ ⊕ r$_j$) ∨ (a$_j$ ∧ b$_j$ ∧ r$_j$) si j ≤ n
* s$_{n+1}$ = r$_{n+1}$
Le nombre de portes du circuit correspondant aux formules ci-dessus est polynômial en n. Aussi, la profondeur du circuit est constante comme le montre le circuit présenté en illustration ci-dessus.
De même la soustraction est dans AC$^0$.

## Exemples de problèmes hors AC$^0$
### Parité

La fonction parité est un prédicat qui renvoie 1 si dans l'entrée le nombre de bits 1 est pair, et qui renvoie 0 sinon. Dans les années 1970, on ne savait pas s'il existait des circuits AC$^0$ pour le problème de la clique ou le problème du voyageur de commerce. En fait, Furst, Saxe et Sipser, et indépendamment Miklós Ajtai ont démontré que ce n'est pas le cas. Ils ont même démontré qu'un prédicat beaucoup plus simple, à savoir la fonction parité, n'appartient pas à AC$^0$. Johan Håstad a ensuite montré un résultat plus fort, le switching lemma (en). Comme la fonction parité est dans NC$^1$, on en déduit que l'inclusion de AC$^0$ dans NC$^1$ est stricte.

### Majorité

La fonction majorité prend en entrée n bits et retourne 1 si strictement plus de la moitié des bits valent 1. Cette fonction n'est pas dans AC$^0$. On peut démontrer cela par l'absurde, si majorité est dans AC$^0$, en ajoutant des bits supplémentaires, on peut tester si x ≥ k, où x est l'entier représenté par les bits en question et k est une constante ; à partir de là on peut tester si x = k ; et donc tester la parité, tout en étant dans AC$^0$, ce qui est une contradiction.

### Multiplication

La multiplication n'est pas dans AC$^0$ et on le montre par réduction depuis la fonction parité. En revanche, elle est dans NC$^1$.

### Primalité

Le prédicat primalité qui teste si un nombre entier est premier n'est pas dans AC$^0$.

## Complexité descriptive

La classe AC$^0$ est liée à la logique du premier ordre en complexité descriptive.