AC0

Diagrama d'un circuit AC0. Els n bits d'entrada estan a la part de baix i la porta de la part superior genera una sola sortida. El circuit consisteix en portes AND i OR de fan-in polinòmic.

La classe de complexitat AC0 és usada en complexitat de circuits. És la classe més petita a la jerarquia AC i consisteix en totes les famílies de circuits de profunditat O(1) i mida polinòmica, amb portes AND i OR amb fan-in il·limitat (només es permeten portes NOT a les entrades). Per tant conté la classe NC0, que conté portes amb fan-in limitat.[1]

La suma i resta d'enters son computables a AC0, però la multiplicació i la divisió no ho son (almenys sota la representació binaria o base 10 d'enters).[2]

Referències

  1. ↑ Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264. 
  2. ↑ Barrington, David Mix; Maciel, Alexis IAS/PCMI Summer Session 2000, Clay Mathematics Undergraduate Program: Basic Course on Computational Complexity., 2000.
  • Vegeu aquesta plantilla
Classes de complexitat
Considerades tractables
DLOGTIME  · AC0  · ACC0  · TC0  · L  · SL  · RL  · NL  · NC  · SC  · CC  · P  · P-complet  · ZPP  · RP  · BPP  · BQP  · APX
Suposadament intractables
UP  · NP  · NP-complet  · NP-hard  · co-NP  · co-NP-complet  · AM  · QMA  · PH  · ⊕P  · PP  · ♯P  · ♯P-complet  · IP  · PSPACE  · PSPACE-complet
Considerades intractables
EXPTIME  · NEXPTIME  · EXPSPACE  · ELEMENTARY  · PR  · R  · RE  · ALL
Jerarquia de classes
Families de classes