Calculer le ième bit de la somme de deux nombres a et b est dans AC0. L'image montre un circuit de taille polynomiale en la taille de l'entrée, ie. 2n et de profondeur constante (ici de profondeur 5 pour tout n).
La classe AC0 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[1],[2] (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[2]. Elle fait partie de la hiérarchie AC.
Exemples
L'addition est dans AC0. 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 AC0.
Détails sur un circuit de taille polynomiale et de profondeur constante pour l'addition
Voici une façon de construire[3] un circuit pour calculer le ième bit de la somme de an-1...a0 et bn-1...b0. Notons ∧ le "et" logique, ∨ le "ou" logique et ⊕ le ou exclusif. On considère aj comme une proposition, vraie si le jème bit de a vaut 1, et fausse sinon. De même, bj comme une proposition, vraie si le jème bit de b vaut 1, et fausse sinon. De même, on note sj comme une proposition, vraie si le jème bit de s vaut 1, et fausse sinon. On introduit également d'autres propositions :
rj est vraie s'il y a une retenue pour le jème bit, fausse sinon ;
gj est vraie si une retenue est générée au jème bit, fausse sinon ;
pj est vraie si la retenue éventuelle est propagée au jème bit, fausse sinon.
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 AC0.
Exemples de problèmes hors AC0
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[réf. nécessaire], on ne savait pas s'il existait des circuits AC0 pour le problème de la clique ou le problème du voyageur de commerce[1]. En fait, Furst, Saxe et Sipser[4], et indépendamment Miklós Ajtai[5] 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 à AC0. Johan Håstad a ensuite montré un résultat plus fort[1], le switching lemma(en)[6]. Comme la fonction parité est dans NC1, on en déduit que l'inclusion de AC0 dans NC1 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 AC0. On peut démontrer cela par l'absurde[7], si majorité est dans AC0, 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 AC0, ce qui est une contradiction.
Multiplication
La multiplication n'est pas dans AC0 et on le montre par réduction depuis la fonction parité[8]. En revanche, elle est dans NC1.
Primalité
Le prédicat primalité qui teste si un nombre entier est premier n'est pas dans AC0[9].
↑Miklós Ajtai, « ∑ 1 1-formulae on finite structures », Annals of pure and applied logic, vol. 24, no 1, , p. 1-48
↑Johan Håstad, « Almost Optimal Lower Bounds for Small Depth Circuits », dans Proceedings of the 18th Annual {ACM} Symposium on Theory of Computing,
May 28-30, 1986, Berkeley, California, {USA}, (DOI10.1145/12130.12132), p. 6-20
