CA (complejidad)

En complejidad de circuitos , AC es una jerarquía de clases de complejidad . Cada clase, AC ⁱ , consta de los lenguajes reconocidos por circuitos booleanos con profundidad${\displaystyle O(\log ^{i}n)}$y un número polinomial de puertas AND y OR con fan-in ilimitado .

El nombre "AC" fue elegido por analogía con NC , donde la "A" en el nombre significa "alternativo" y hace referencia tanto a la alternancia entre las puertas AND y OR en los circuitos como a las máquinas de Turing alternantes . ^{[ 1 ]}

La clase de corriente alterna más pequeña es la AC ⁰ , que consta de circuitos de entrada de ventilador ilimitados de profundidad constante.

La jerarquía total de clases AC se define como

${\displaystyle {\mbox{AC}}=\bigcup _{i\geq 0}{\mbox{AC}}^{i}}$

Las clases AC están relacionadas con las clases NC , ACC y TC . Para cada i , tenemos ^{[ 2 ]}

${\displaystyle {\mathsf {NC}}^{i}\subseteq {\mathsf {AC}}^{i}\subseteq {\mathsf {ACC}}^{i}\subseteq {\mathsf {TC}}^{i}\subseteq {\mathsf {NC}}^{i+1}.}$

Como consecuencia inmediata de esto, tenemos que NC = AC = ACC = TC. ^{[ 3 ]}

Tenemos${\displaystyle {\mathsf {NC}}^{0}\subsetneq {\mathsf {AC}}^{0}\subsetneq {\mathsf {ACC}}^{0}}$. Específicamente, PARITY está en${\displaystyle {\mathsf {ACC}}^{0}}$pero no en${\displaystyle {\mathsf {AC}}^{0}}$. ^{[ 4 ]} Y dado que NC requiere un fan-in limitado, cualquier función de tipo${\displaystyle \{0,1\}^{n}\to \{0,1\}}$cuyo resultado depende de más que${\displaystyle O(1)}$Las entradas están más allá${\displaystyle {\mathsf {NC}}^{0}}$. En particular, el OR de fan-in ilimitado está más allá${\displaystyle {\mathsf {NC}}^{0}}$.

En detalle, defina${\displaystyle f_{n}:\{0,1\}^{n}\to \{0,1\}}$por${\displaystyle f_{n}(x_{1},\dots ,x_{n})=\sum _{i}x_{i}\mod 2}$Entonces requiere${\displaystyle \Omega (2^{\frac {n^{1/d}}{16}})}$puertas que deben ser calculadas por un${\displaystyle {\mathsf {AC}}^{0}}$circuito con profundidad${\displaystyle \leq d}$. ^{[ 5 ]}

La potencia de las clases AC puede verse afectada al añadir compuertas adicionales. Si añadimos compuertas que calculan la operación de módulo para algún módulo m , tenemos las clases ACC ⁱ [m] . ^{[ 3 ]}

• Arora, Sanjeev ; Barak, Boaz (2009), Complejidad computacional: un enfoque moderno , Cambridge University Press , ISBN 978-0-521-42426-4, Zbl 1193.68112 
• Clote, Peter; Kranakis, Evangelos (2002), Boolean Functions and Computation Models , Texts in Theoretical Computer Science: An EATCS Series, Berlín: Springer-Verlag , ISBN 3-540-59436-1, Zbl 1016.94046 
• Pitassi, Toniann (otoño de 2015), "Conferencia n.° 8" (PDF) , CS 2401 – Introducción a la teoría de la complejidad , Universidad de Toronto
• Razborov, AA (abril de 1987), "Límites inferiores del tamaño de circuitos de profundidad acotada sobre una base completa con suma lógica" , Notas Matemáticas de la Academia de Ciencias de la URSS , 41 (4): 333–338 , doi : 10.1007/BF01137685 , ISSN 0001-4346 
• Regan, Kenneth W. (1999), "Clases de complejidad", Manual de algoritmos y teoría de la computación , CRC Press.
• Vollmer, Heribert (1998), Introducción a la complejidad de circuitos. Un enfoque uniforme , Textos en Ciencias de la Computación Teórica, Berlín: Springer-Verlag , ISBN 3-540-64310-9, Zbl 0931.68055