ACC0
ACC0, à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 AC0 de "circuitos alternados" de profundidade constante com a capacidade de contar; a sigla ACC significa "AC com contadores"[1] Especificamente, um problema pertence a ACC0 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. ACC0 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
[editar | editar código-fonte]Informalmente, ACC0 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 AC0 [m] se pode ser computada por uma família de circuitos C1, C2, ..., onde Cn possui n entradas, a profundidade de todos os circuitos é constante, o tamanho de Cn é 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 ACC0, se ele pertence a AC0[m] para algum m.
Em alguns textos, ACCi refere-se a uma hierarquia de classes de circuito com ACC0, em seu nível mais baixo, onde os circuitos em ACCi tem profundidade O(login) e tamanho polinomial.[1]
A classe ACC0 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 ACC0 é 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
[editar | editar código-fonte]A classe ACC0 inclui AC0. 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 AC0. De modo mais geral, a função MODm não pode ser calculada em AC0[p] para p primo, a menos que m seja uma potência de p.[3]
A classe ACC0 está incluída em TC0. Conjectura-se que ACC0 é incapaz de computar a função majoritária de suas entradas (ou seja, a inclusão em TC0 é rigorosa), mas isso continua sem solução desde Julho de 2014.
Todo problema em ACC0 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 ACC0 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 ACC0 via circuitos SYM+. [5]
Sabe-se que o cálculo do permanente é impossível para circuitos ACC0 de tempo logaritmico uniforme, o que implica que a classe de complexidade PP não está contida em ACC0 em tempo logaritmico uniforme.[6]
Notas
[editar | editar código-fonte]Referências
[editar | editar código-fonte]- 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 NC1» (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 NC1», 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.