Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è ACC0.ACC0, a volte chiamata ACC, è una classe di modelli e problemi computazionali definiti nella complessità dei circuiti, un campo dell'informatica teorica. La classe è definita accrescendo la classe AC0 di "circuiti alternanti" a profondità costante con la capacità di contare; l'acronimo ACC sta per "AC con contatori".[1] Specificamente, un problema appartiene ad ACC0 se può essere risolto da circuiti in tempo polinomiale e a profondità costante con porte aventi il numero massimo di linee d'ingresso (fan-in) limitato, incluse porte che contano modulo un intero fisso. ACC0 corrisponde alla computazione in qualsiasi monoide risolvibile. La classe è molto ben studiata in informatica teorica a causa delle connessioni algebriche e perché è uno dei più grandi modelli computazionali concreti per i quali possono essere provati i risultati di impossibilità computazionali, i cosiddetti limiti inferiori dei circuiti.
Definizioni
[modifica | modifica wikitesto]Informalmente, ACC0 modella la classe di computazioni realizzate da circuiti booleani di profondità costante e dimensione polinomiale, dove le porte dei circuiti comprendono "porte contatrici modulari" che computano il numero di vere entrate modulo qualche costante fissa.
Più formalmente, un linguaggio appartiene ad AC0[m] se può essere computato da una famiglia di circuiti C1, C2, ..., dove Cn richiede n entrate, la profondità di ogni circuito è costante, la dimensione di Cn è una funzione polinomiale di n, e il circuito usa le porte seguenti: porte AND e porte OR con numero massimo di linee d'ingresso limitato, che computano la congiunzione e la disgiunzione delle entrate; porte NOT che computano la negazione della loro unica entrata; e porte MOD-m con numero massimo di linee d'ingresso illimitato, che computano 1 se il numero di entrata 1s è un multiplo di m. Un linguaggio appartiene ad ACC0 se appartiene ad AC0[m] per un qualche m.
In alcuni testi, ACCi si riferisce a una gerarchia di classi di circuiti con ACC0 al suo livello più basso, dove i circuiti in ACCi hanno profondità O(login) e dimensione polinomiale.[1]
La classe ACC0 può essere definita anche in termini di computazioni di automi finiti deterministici non uniformi (nonuniform deterministic finite automata, NUDFA) sui monoidi. In questa cornice, l'entrata è interpretata come elementi da un monoide fisso, e l'entrata è accettata se il prodotto degli elementi dell'entrata appartiene a una data lista di elementi del monoide. La classe ACC0 è la famiglia di linguaggi accettati da un NUDFA su qualche monoide che non contiene un gruppo irrisolvibile come sottosemigruppo.[2]
Potenza computazionale
[modifica | modifica wikitesto]La classe ACC0 include AC0. Questa inclusione è rigida, perché un'unica porta MOD-2 computa la funzione di parità, che si sa essere impossibile da computare in AC0. Più in generale, la funzione MODm non può essere computata in AC0[p] per un numero primo p a meno che m non sia una potenza di p.[3]
Ogni problema in ACC0 può essere risolta da circuiti di profondità 2, con porte AND con numero massimo di linee d'ingresso polilogaritmico alle entrate, connesse a una porta singola che computa una funzione simmetrica.[4] Questi circuiti sono chiamati circuiti SYM+.
La classe ACC0 è inclusa in TC0.
Ryan Williams annunciò nel 2010 e pubblicò nel 2011 una dimostrazione che ACC0 non contiene NEXPTIME.[5] La dimostrazione usa molti risultati nella teoria della complessità, compresi la teoria della gerarchia temporale, IP = PSPACE, la derandomizzazione e le idee nella dimostrazione del teorema di Toda.[6]
Si sa che computare il permanente è impossibile per i circuiti ACC0 uniformi in tempo logaritmico, il che implica che la classe di complessità PP non è contenuta in ACC0 uniforme in tempo logaritmico.[7]
Si congettura che ACC0 sia incapace di computare la funzione di maggioranza delle sue entrate, ma questo quesito era irrisolto al luglio 2012.
Note
[modifica | modifica wikitesto]Bibliografia
[modifica | modifica wikitesto]- Eric Allender, Circuit complexity before the dawn of the new millennium (PDF), in 16th Conference on Foundations of Software Technology and Theoretical Computer Science,Hyderabad, India, December 18–20, 1996[collegamento interrotto], Lecture Notes in Computer Science, vol. 1180, Springer, 1996, 1–18, DOI:10.1007/3-540-62034-6_33.
- Eric Allender e Vivec Gore, A uniform circuit lower bound for the permanent (PDF), in SIAM Journal on Computing, vol. 23, n. 5, 1994, 1026–1049, DOI:10.1137/S0097539792233907. URL consultato il 21 marzo 2014 (archiviato dall'url originale il 3 marzo 2016).
- D.A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1 (PDF), in Journal of Computer and System Sciences, vol. 38, n. 1, 1989, 150–164, DOI:10.1016/0022-0000(89)90037-8.
- David A. Mix Barrington, Some problems involving Razborov-Smolensky polynomials, in M.S. Paterson (a cura di), Boolean function complexity, Sel. Pap. Symp., Durham/UK 1990, London Mathematical Society Lecture Notes Series, vol. 169, 1992, 109-128, ISBN 0-521-40826-1, Zbl 0769.68041.
- D.A. Barrington e D. Thérien, Finite monoids and the fine structure of NC1, in Journal of the ACM, vol. 35, n. 4, 1988, 941–952, DOI:10.1145/48014.63138.
- Richard Beigel e Jun Tarui, On ACC, in Computational Complexity, vol. 4, 1994, 350–366, DOI:10.1007/BF01263423.
- Peter Clote e Evangelos Kranakis, Boolean functions and computation models, Texts in Theoretical Computer Science. An EATCS Series, Berlino, Springer-Verlag, 2002, ISBN 3-540-59436-1, Zbl 1016.94046.
- A. A. Razborov, Lower bounds for the size of circuits of bounded depth with basis {⊕,∨}, in Math. notes of the Academy of Science of the USSR, vol. 41, n. 4, 1987, 333–338.
- R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proc. 19th ACM Symposium on Theory of Computing, 1987, 77–82, DOI:10.1145/28395.28404.
- D. Thérien, Classification of finite monoids: The language approach, in Theoretical Computer Science, vol. 14, n. 2, 1981, 195–208, DOI:10.1016/0304-3975(81)90057-8.
- Heribert Vollmer, Introduction to Circuit Complexity, Berlino, Springer, 1999, ISBN 3-540-64310-9.
- Ryan Williams, Non-uniform ACC Circuit Lower Bounds (PDF), in IEEE Conf. on Computational Complexity, 2011, 115–125, DOI:10.1109/CCC.2011.36.
