Vés al contingut

ACC0

De la Viquipèdia, l'enciclopèdia lliure
Diagrama d'un circuit ACC0: per un nombre fixat m, el circuit consisteix en portes AND, OR i NOT i (Mod m). El fan-in de cada porta està fitat per un polinomi i la profunditat del circuit per una constant.

La classe de complexitat ACC0 és usada en complexitat de circuits. La classe ACC0 es defineix augmentant la classe AC0 amb l'habilitat de comptar, l'acrònim significa "AC amb comptadors". Específicament, un problema pertany a ACC0 si es pot resoldre per un circuit de portes de fan-in il·limitat amb una mida polinòmica, una profunditat constant incloent portes que poden comptar amb mòdul un valor fixat.[1]

Relació amb d'altres classes

[modifica]

La classe ACC0 conté la classe AC0. Aquesta inclusió és estricta perquè una sola porta MOD-2 computa la funció paritat, que se sap que és impossible d'implementar a AC0. Més generalment, la funció MOD-m no es pot computar a ACC0[p] per p primer llevat que m sigui una potència de p.[2]

La classe ACC0 està inclous a dins de TC0. Se suposa que ACC0 és incapaç de computar la funció majoria de les seves entrades (la inclusió és estricta), però a 2018 no s'ha resolt.

Tot problema dins d'ACC0 es pot resoldre amb circuits de profunditat 2, amb portes AND de fan-in polilogarítmic a les entrades, connectat a una sola porta computant la funció simètrica.[3] Aquests circuits s'anomenen circuits-SYM+.

El 2011 es va demostrar que ACC0 no conté NEXPTIME.[4]

Referències

[modifica]
  1. ↑ 1964-, Vollmer, Heribert,. Introduction to circuit complexity : a uniform approach. Berlín: Springer, 1999. ISBN 3540643109. 
  2. ↑ Razborov, A. A. «Lower bounds for the size of circuits of bounded depth with basis {⊕,∨}». Math. notes of the Academy of Science of the USSR, 1987, pàg. 333–338.
  3. ↑ Beigel, Richard; Tarui, Jun «On ACC» (en anglès). Computational Complexity, 4, 4, 12-1994, pàg. 350–366. DOI: 10.1007/bf01263423. ISSN: 1016-3328.
  4. ↑ Williams, Ryan «Non-uniform ACC Circuit Lower Bounds» (en anglès). IEEE Conf. on Computational Complexity. IEEE, 6-2011. DOI: 10.1109/ccc.2011.36.
Obtingut de «https://ca.wikipedia.org/w/index.php?title=ACC0&oldid=28884057»