AC (complejidad)
En la teoría de la complejidad , AC es la clase de complejidad definida como la unión de AC i , donde AC i es la clase de complejidad de problemas decididos por circuitos booleanos de profundidad , de tamaño polinómico, cuyas puertas son AND y OR, de grados entrantes ilimitados (en De hecho, se pueden permitir otras puertas como "exclusivas OR" o NOT porque son expresables, sin cambiar la complejidad, mediante AND y OR).
En particular, AC 0 es la clase de complejidad de los problemas decididos por circuitos booleanos de profundidad constante, de tamaño polinómico.
AC = NC
Las clases NC y NC i son análogas a AC y AC i excepto que la aridad de las puertas lógicas está limitada. Se tiene :
Por tanto, las clases AC y NC son iguales.