Vés al contingut

AC0

De la Viquipèdia, l'enciclopèdia lliure
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

[modifica]
  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.
Obtingut de «https://ca.wikipedia.org/w/index.php?title=AC0&oldid=28884055»