ACC0
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
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
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à, compresa 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
- ^ a b Vollmer (1999), p. 126
- ^ Thérien (1981), Barrington & Thérien (1988)
- ^ Razborov (1987), Smolensky (1987)
- ^ Beigel & Tarui (1994)
- ^ Williams (2011).
- ^ (EN) Aggiunta al libro di Arora & Barak (PDF), su cs.princeton.edu.
- ^ Allender & Gore (1994)
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. URL consultato il 21 marzo 2014 (archiviato dall'url originale il 3 marzo 2016).
- 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.
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.