ACC0

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è ACC⁰.

ACC⁰, 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 AC⁰ di "circuiti alternanti" a profondità costante con la capacità di contare; l'acronimo ACC sta per "AC con contatori". Specificamente, un problema appartiene ad ACC⁰ 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. ACC⁰ 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

Informalmente, ACC⁰ 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 AC⁰[m] se può essere computato da una famiglia di circuiti C₁, C₂, ..., dove C_n richiede n entrate, la profondità di ogni circuito è costante, la dimensione di C_n è 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 ACC⁰ se appartiene ad AC⁰[m] per un qualche m.

In alcuni testi, ACCⁱ si riferisce a una gerarchia di classi di circuiti con ACC⁰ al suo livello più basso, dove i circuiti in ACCⁱ hanno profondità O(logⁱn) e dimensione polinomiale.

La classe ACC⁰ 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 ACC⁰ è la famiglia di linguaggi accettati da un NUDFA su qualche monoide che non contiene un gruppo irrisolvibile come sottosemigruppo.

Potenza computazionale

La classe ACC⁰ include AC⁰. Questa inclusione è rigida, perché un'unica porta MOD-2 computa la funzione di parità, che si sa essere impossibile da computare in AC⁰. Più in generale, la funzione MOD_m non può essere computata in AC⁰[p] per un numero primo p a meno che m non sia una potenza di p.

Ogni problema in ACC⁰ 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. Questi circuiti sono chiamati circuiti SYM⁺.

La classe ACC⁰ è inclusa in TC⁰.

Ryan Williams annunciò nel 2010 e pubblicò nel 2011 una dimostrazione che ACC⁰ non contiene NEXPTIME. 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.

Si sa che computare il permanente è impossibile per i circuiti ACC⁰ uniformi in tempo logaritmico, il che implica che la classe di complessità PP non è contenuta in ACC⁰ uniforme in tempo logaritmico.

Si congettura che ACC⁰ sia incapace di computare la funzione di maggioranza delle sue entrate, ma questo quesito era irrisolto al luglio 2012.

Bibliografia

• 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, 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 NC¹ (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 NC¹, 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.