AC (complexité)

classe de complexité

En théorie de la complexité, AC est la classe de complexité définie comme l'union des ACi, où ACi est la classe de complexité des problèmes décidés par des circuits booléens de profondeur , 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és comme des portes "OU exclusif" ou NON car elles sont exprimables, sans changer la complexité, par des ET et des OU).

En particulier, AC0 est la classe de complexité des problèmes décidés par des circuits booléens de profondeur constante, de taille polynomiale.

AC = NC

modifier

Les classes NC et NCi sont analogues à AC et ACi sauf que l'arité des portes logiques est borné. On a :

 

Ainsi, les classes AC et NC sont égales.

Liens externes

modifier

(en) La classe AC sur le Complexity Zoo