Loading AI tools
classe de complexité De Wikipédia, l'encyclopédie libre
En théorie de la complexité, AC0 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 AC0 contient l'addition, mais pas la fonction parité, la multiplication ou le prédicat de primalité (voir plus bas).
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.
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.
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 :
On a :
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.
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.
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.
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.
Le prédicat primalité qui teste si un nombre entier est premier n'est pas dans AC0[9].
La classe AC0 est liée à la logique du premier ordre en complexité descriptive[10].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
