En la complejidad del circuito , AC es una jerarquía de clases de complejidad . Cada clase, AC i , consta de los lenguajes reconocidos por circuitos booleanos con profundidady un número polinomial de compuertas Y y O de entrada en abanico ilimitadas .
El nombre "AC" se eligió por analogía con NC , con la "A" en el nombre que significa "alternar" y se refiere tanto a la alternancia entre las puertas AND y OR en los circuitos como a las máquinas de Turing alternas . [1]
La clase de CA más pequeña es CA 0 , que consta de circuitos de entrada de ventilador ilimitados de profundidad constante.
La jerarquía total de clases de CA se define como
Relación con NC
Las clases de CA están relacionadas con las clases de NC , que se definen de manera similar, pero con puertas que solo tienen un ventilador constante. Para cada i , tenemos [2] [3]
Como consecuencia inmediata de esto, tenemos que NC = AC. [4]
Se sabe que la inclusión es estricta para i = 0. [3]
Variaciones
La potencia de las clases de CA puede verse afectada al agregar puertas adicionales. Si agregamos puertas que calculan la operación de módulo para algún módulo m , tenemos las clases ACC i [m] . [4]
Notas
- ^ Regan (1999) , página 27-18.
- ^ Clote y Kranakis (2002 , p. 437)
- ↑ a b Arora y Barak (2009 , p. 118)
- ↑ a b Clote y Kranakis (2002 , p. 12)
Referencias
- 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), Funciones booleanas y modelos de computación , Textos en Informática Teórica. Una serie EATCS, Berlín: Springer-Verlag , ISBN 3-540-59436-1, Zbl 1016.94046
- 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 los circuitos. Un enfoque uniforme , Textos en informática teórica, Berlín: Springer-Verlag , ISBN 3-540-64310-9, Zbl 0931.68055