CA ⁰ -AC⁰

Schéma d'un circuit AC ⁰ : Les n bits d'entrée sont en bas et la porte du haut produit la sortie ; le circuit se compose de portes ET et OU d'éventail polynomial chacune, et la profondeur d'alternance est délimitée par une constante.

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 ET et des portes OU à fanin illimité . (Nous n'autorisons PAS de portes uniquement aux entrées). Il contient donc NC ⁰ , qui n'a que des portes ET et OU à fanin borné.

Exemples de problèmes

L'addition et la soustraction d'entiers sont calculables dans AC ⁰ , mais pas la multiplication (du moins, pas sous les représentations binaires ou en base 10 habituelles des entiers).

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

Complexité descriptive

Du point de vue de la 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 bien par FO(+, ×), ou par Turing machine dans la hiérarchie logarithmique .

Séparations

En 1984, Furst, Saxe et Sipser ont montré que le calcul de la parité d'une entrée ne peut être décidé par aucun circuit AC ⁰ , même en cas de 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 changement de lemme . En les utilisant, il a été montré qu'il existe une séparation oracle entre la hiérarchie polynomiale et PSPACE .

Les références