CA 0

AC ⁰ (circuito alterno) es una clase de complejidad utilizada en complejidad de circuitos . Es la clase más pequeña en la jerarquía AC y consta de todas las familias de circuitos de profundidad O(1) y tamaño polinomial, con puertas AND y OR de fanin ilimitado (solo permitimos puertas NOT en las entradas). ^{[ 1 ]} Por lo tanto, contiene NC ⁰ , que tiene solo puertas AND y OR de fanin limitado. ^{[ 1 ]} Dichos circuitos se denominan "circuitos alternos", ya que solo es necesario que las capas alternen entre todas AND y todas OR, puesto que una AND después de otra AND es equivalente a una sola AND, y lo mismo para OR.

La suma y la resta de enteros son computables en AC ⁰ , ^{[ 2 ]} pero la multiplicación no lo es (específicamente, cuando las entradas son dos enteros bajo las representaciones binarias habituales ^{[ 3 ]} o de base 10 de enteros).

Dado que es una clase de circuito, como P/poly , AC ⁰ también contiene todos los lenguajes unarios .

Desde el punto de vista de la complejidad descriptiva , DLOGTIME - uniforme AC ⁰ es igual a la clase descriptiva FO +BIT de todos los lenguajes descriptibles en lógica de primer orden con la adición del predicado BIT , o alternativamente por FO(+, ×), o por máquina de Turing en la jerarquía logarítmica . ^{[ 4 ]}

En 1984, Furst, Saxe y Sipser demostraron que calcular la PARIDAD de los bits de entrada (a diferencia de los problemas de suma/resta mencionados anteriormente que tenían dos entradas) no puede ser decidido por ningún circuito AC ⁰ , incluso con no uniformidad. De manera similar, calcular la mayoría tampoco es posible.${\displaystyle {\mathsf {AC}}^{0}}$. ^{[ 5 ] [ 1 ]} De ello se deduce que AC ⁰ es estrictamente menor que TC ⁰ . Nótese que "PARIDAD" también se denomina " XOR " en la literatura.

Sin embargo, PARITY apenas está fuera de AC ⁰ , en el sentido de que para cualquier${\displaystyle k>0}$Existe una familia de circuitos alternos que utilizan profundidad${\displaystyle \lceil k\ln n/\ln \ln n\rceil }$y tamaño${\displaystyle O\left(2^{(\ln n)^{1/k}}{\frac {n}{(\ln n)^{1/k}}}\right)}$. ^{[ 6 ] : 135} En particular, estableciendo${\displaystyle k}$Si es una constante grande, entonces existe una familia de circuitos alternos que utilizan profundidad${\displaystyle O(\ln n/\ln \ln n)\ll O(\ln n)}$y el tamaño es solo ligeramente superlineal.

${\displaystyle {\mathsf {AC}}^{0}}$se puede dividir aún más, en una jerarquía de lenguajes que requieren hasta 1 capa, 2 capas, etc.${\displaystyle {\mathsf {AC}}_{d}^{0}}$sea ​​la clase de lenguajes decidibles por una familia de circuitos umbral de hasta profundidad${\displaystyle d}$:$${\displaystyle {\mathsf {AC}}_{1}^{0}\subset {\mathsf {AC}}_{2}^{0}\subset \cdots \subset {\mathsf {AC}}^{0}=\bigcup _{d=1}^{\infty }{\mathsf {AC}}_{d}^{0}}$$El siguiente problema es${\displaystyle {\mathsf {AC}}_{d}^{0}}$-completar bajo una condición de uniformidad: dado un gráfico de cuadrícula de longitud y ancho polinomiales${\displaystyle d}$, decidir si dos vértices dados están conectados. ^{[ 7 ]}

La adición de dos${\displaystyle n}$Los enteros de -bits están en${\displaystyle {\mathsf {AC}}_{3}^{0}}$pero no en${\displaystyle {\mathsf {AC}}_{2}^{0}}$. ^{[ 6 ] : 148}