ACC0

Esboço de um circuito ACC: Para um número fixo m, o circuito consiste das portas lógicas NOT, AND, OR, e (Mod m). O fator de carga de entrada de cada porta lógica é delimitada por um polinômio e a profundidade do circuito é delimitada por uma constante.

ACC^0, às vezes chamado de ACC, é uma classe de modelos computacionais e problemas definidos em complexidade do circuito, uma área da teoria da computação. A classe é definida aumentando a classe AC^0 de "circuitos alternados" de profundidade constante com a capacidade de contar; a sigla ACC significa "AC com contadores"[1] Especificamente, um problema pertence a ACC^0 se ele pode ser resolvido por circuitos de profundidade constante com portas lógicas de entrada ilimitadas, de tamanho polinomial, incluindo portas que calculam o MOD de um inteiro fixado. ACC^0 corresponde a computação em qualquer monóide solúvel. A classe é muito bem estudada em teoria da computação por causa das conexões algébricas e porque é um dos maiores modelos computacionais concretos para os quais resultados computacionais de impossbilidade, os chamados limitantes inferiores de circuitos, podem ser provados.

Definições

Informalmente, ACC^0 modela a classe de cálculos realizados por circuitos booleanos de profundidade constante e tamanho polinomial, onde as portas do circuito incluem "portas de contagem modular" que calculam o resto da divisão entre o número de entradas verdadeiras por alguma constante fixa.

Mais formalmente, uma linguagem pertence a AC^0 [m] se pode ser computada por uma família de circuitos C₁, C₂, ..., onde C_n possui n entradas, a profundidade de todos os circuitos é constante, o tamanho de C_n é uma função polinomial da variável n, e o circuito utiliza as seguintes portas: portas lógicas AND e portas lógicas OR com fator de carga de entrada irrestrita, calculando a conjunção e a disjunção das suas entradas; Porta lógica NOT computa a negação de sua única entrada; e fator de carga de entrada ilimitada em portas lógicas MOD-m, que computam 1 se o número de 1s na entrada é um múltiplo de m. Uma linguagem pertence a ACC^0, se ele pertence a AC^0[m] para algum m.

Em alguns textos, ACC^i refere-se a uma hierarquia de classes de circuito com ACC^0, em seu nível mais baixo, onde os circuitos em ACC^i tem profundidade O(log^in) e tamanho polinomial.[1]

A classe ACC^0 também pode ser definida em termos da computação de autômatos finitos determinísticos não-uniformes (AFDNU) sobre monóides. Nessa abordagem, a entrada é interpretada como elementos de uma monóide fixa, e a entrada é aceita se o produto dos elementos de entrada pertencerem a uma determinada lista de elementos da monóide. A classe ACC^0 é a família das linguagens aceitas por um AFDNU sobre alguns monóides que não contém grupos insolúveis como um subsemigrupo.[2]

Poder computacional

A classe ACC^0 inclui AC^0. Esta inclusão é rigorosa, porque uma única porta MOD-2 calcula a função de paridade, que é conhecido por ser impossível de calcular em AC^0. De modo mais geral, a função MOD_m não pode ser calculada em AC^0[p] para p primo, a menos que m seja uma potência de p.[3]

A classe ACC^0 está incluída em TC^0. Conjectura-se que ACC^0 é incapaz de computar a função majoritária de suas entradas (ou seja, a inclusão em TC^0 é rigorosa), mas isso continua sem solução desde Julho de 2014.

Todo problema em ACC^0 pode ser resolvido por circuitos de profundidade 2, com portas lógicas AND com fator de carga de entrada polilogaritmico nas entradas, ligado a uma única porta computando uma função simétrica.[4] Esses circuitos são chamados circuitos SYM^+. A prova segue idéias da prova do teorema de Toda.

Williams (2011) prova que ACC^0 não contém NEXPTIME. A prova utiliza muitos resultados em teoria da complexidade, incluindo o teorema da hierarquia de tempo, IP = PSPACE, derandomization, e a representação da ACC^0 via circuitos SYM^+. [5]

Sabe-se que o cálculo do permanente é impossível para circuitos ACC^0 de tempo logaritmico uniforme, o que implica que a classe de complexidade PP não está contida em ACC^0 em tempo logaritmico uniforme.[6]

Notas

1. Vollmer (1999),p. 126
2. Thérien (1981), Barrington & Thérien (1988)
3. Razborov (1987), Smolensky (1987)
4. Beigel & Tarui (1994)
5. Addendum to Arora, Barak textbook
6. Allender & Gore (1994)

Referências

• Eric Allender (1996), «Circuit complexity before the dawn of the new millennium», 16th Conference on Foundations of Software Technology and Theoretical Computer Science,Hyderabad, India, December 18–20, 1996 (PDF), Lecture Notes in Computer Science, 1180, Springer, pp. 1–18, doi:10.1007/3-540-62034-6_33 
• Eric Allender; Gore, Vivec (1994), «A uniform circuit lower bound for the permanent» (PDF), SIAM Journal on Computing, 23 (5): 1026–1049, doi:10.1137/S0097539792233907 
• Barrington, D.A. (1989), «Bounded-width polynomial-size branching programs recognize exactly those languages in NC^1» (PDF), Journal of Computer and System Sciences, 38 (1): 150–164, doi:10.1016/0022-0000(89)90037-8 .
• Barrington, David A. Mix (1992), «Some problems involving Razborov-Smolensky polynomials», in: Mike Paterson, Boolean function complexity, Sel. Pap. Symp., Durham/UK 1990., ISBN 0-521-40826-1, London Mathematical Society Lecture Notes Series, 169, pp. 109–128, Zbl 0769.68041 .
• Barrington, D.A.; Thérien, D. (1988), «Finite monoids and the fine structure of NC^1», Journal of the ACM, 35 (4): 941–952, doi:10.1145/48014.63138 
• Beigel, Richard; Tarui, Jun (1994), «On ACC», Computational Complexity, 4: 350–366, doi:10.1007/BF01263423 .
• Clote, Peter; Kranakis, Evangelos (2002), Boolean functions and computation models, ISBN 3-540-59436-1, Texts in Theoretical Computer Science. An EATCS Series, Berlin: Springer-Verlag, Zbl 1016.94046 
• Razborov, A. A. (1987), «Lower bounds for the size of circuits of bounded depth with basis {⊕,∨}», Math. notes of the Academy of Science of the USSR, 41 (4): 333–338 .
• Smolensky, R. (1987), «Algebraic methods in the theory of lower bounds for Boolean circuit complexity», Proc. 19th ACM Symposium on Theory of Computing, pp. 77–82, doi:10.1145/28395.28404 .
• Thérien, D. (1981), «Classification of finite monoids: The language approach», Theoretical Computer Science, 14 (2): 195–208, doi:10.1016/0304-3975(81)90057-8 .
• Vollmer, Heribert (1999), Introduction to Circuit Complexity, ISBN 3-540-64310-9, Berlin: Springer .
• Ryan Williams (2011), «Non-uniform ACC Circuit Lower Bounds» (PDF), IEEE Conf. on Computational Complexity: 115–125, doi:10.1109/CCC.2011.36 .