En la teoría de la complejidad , AC 0 es una clase de complejidad definida por circuitos booleanos de profundidad constante. Es parte de la jerarquía AC . La clase AC 0 contiene la suma, pero no la función de paridad, la multiplicación o el predicado de primalidad (ver más abajo).
La clase AC 0 es la clase de complejidad de problemas determinados por circuitos booleanos de profundidad constante, tamaño polinomial, las puertas son Y y O , grados entrantes ilimitados (de hecho, se pueden permitir otras puertas como " O exclusivo " o puertas NO porque son expresable, sin cambiar la complejidad, por AND y OR ). El acrónimo AC proviene de circuito de alternancia . Es parte de la jerarquía AC .
La adición está en AC 0 . Más precisamente, para todo i, el problema de decisión que toma como entrada 2n bits que representan dos números ayb de n bits y que calcula el i- ésimo bit de la suma de ayb está en AC 0 .
Detalles sobre un circuito de tamaño polinomial y profundidad constante para sumarAquí hay una forma de construir un circuito para calcular el i- ésimo bit de la suma de a n-1 ... a 0 y b n-1 ... b 0 . Tenga en cuenta la ∧ "y" lógica, ∨ la lógica "o" y ⊕ exclusiva o. Consideramos a j como una proposición, verdadera si el j- ésimo bit de a es igual a 1 y falsa en caso contrario. Del mismo modo, b j como proposición, verdadero si el j- ésimo bit de b es igual a 1, y falso en caso contrario. Asimismo, denotamos por s j como una proposición, verdadera si el j- ésimo bit de s es 1 y falsa en caso contrario. También presentamos otras propuestas:
Se tiene :
El número de puertas en el circuito correspondiente a las fórmulas anteriores es polinomio en n. Además, la profundidad del circuito es constante, como se muestra en el circuito que se muestra en la ilustración anterior.
Asimismo, la resta está en AC 0 .
La función de paridad es un predicado que devuelve 1 si en la entrada el número de bits 1 es par, y que devuelve 0 en caso contrario. En la década de 1970 , no se sabía si había circuitos AC 0 para el problema de la camarilla o el problema del viajante . De hecho, Furst, Saxe y Sipser , e independientemente Miklós Ajtai han demostrado que no es así. Incluso demostraron que un predicado mucho más simple, a saber, la función de paridad , no pertenece a AC 0 . Johan Håstad mostró entonces un resultado más fuerte, el lema de cambio (adentro) . Como la función de paridad está en NC 1 , deducimos que la inclusión de AC 0 en NC 1 es estricta.
La función mayoritaria toma n bits como entrada y devuelve 1 si estrictamente más de la mitad de los bits son iguales a 1. Esta función no está en AC 0 . Podemos demostrar esto absurdamente, si la mayoría está en AC 0 , agregando bits adicionales, podemos probar si x ≥ k , donde x es el número entero representado por los bits en cuestión y k es una constante; a partir de ahí podemos probar si x = k ; y por lo tanto probar la paridad , estando en AC 0 , lo cual es una contradicción.
La multiplicación no está en AC 0 y se muestra por reducción de la función de paridad. Por otro lado, está en NC 1 .
El predicado de primalidad que prueba si un número entero es primo no está en AC 0 .
La clase AC 0 está relacionada con la lógica de primer orden en complejidad descriptiva .