AC0

AC ⁰ est une classe de complexité utilisée dans la complexité des circuits . C'est la plus petite classe de la hiérarchie AC , et se compose de toutes les familles de circuits de profondeur O(1) et de taille polynomiale, avec des portes AND et des portes OR à fanin illimité (nous autorisons les portes NOT uniquement aux entrées). Elle contient donc NC ⁰ , qui n'a que des portes AND et OR à fanin limité.

L'addition et la soustraction d'entiers sont calculables dans AC ⁰ , mais la multiplication ne l'est pas (en particulier, lorsque les entrées sont deux entiers sous les représentations binaires habituelles ou en base 10 des entiers).

Puisqu'il s'agit d'une classe de circuit, comme P/poly , AC ⁰ contient également tous les langages unaires .

D'un point de vue de complexité descriptive , DLOGTIME - uniforme AC ⁰ est égal à la classe descriptive FO + BIT de tous les langages descriptibles en logique du premier ordre avec l'ajout du prédicat BIT , ou alternativement par FO(+, ×), ou par la machine de Turing dans la hiérarchie logarithmique .

En 1984, Furst, Saxe et Sipser ont montré que le calcul de la parité des bits d'entrée (contrairement aux problèmes d'addition/soustraction mentionnés ci-dessus qui avaient deux entrées) ne peut pas être décidé par aucun circuit AC ⁰ , même avec non-uniformité. Il s'ensuit que AC ⁰ n'est pas égal à NC ¹ , car une famille de circuits de cette dernière classe peut calculer la parité. Des limites plus précises découlent du lemme de commutation . En les utilisant, il a été démontré qu'il existe une séparation oracle entre la hiérarchie polynomiale et PSPACE .