AC 0 es una clase de complejidad utilizada en la complejidad de circuitos . Es la clase más pequeña en la jerarquía de CA y consta de todas las familias de circuitos de profundidad O (1) y tamaño polinomial, con puertas AND y OR de fanin ilimitado . (Permitimos NO puertas solo en las entradas). [1] Por lo tanto, contiene NC 0 , que solo tiene compuertas AND y OR de ventilador acotado. [1]
Problemas de ejemplo
La suma y resta de enteros se pueden calcular en AC 0 , [2] pero la multiplicación no lo es (al menos, no bajo las representaciones binarias o en base 10 habituales de los enteros).
Dado que es una clase de circuito, como P / poly , AC 0 también contiene todos los lenguajes unarios .
Complejidad descriptiva
Desde un punto de vista de complejidad descriptiva , DLOGTIME - uniforme AC 0 es igual a la clase descriptiva FO + BIT de todos los lenguajes que se pueden describir en lógica de primer orden con la adición del predicado BIT , o alternativamente por FO (+, ×), o por Turing máquina en la jerarquía logarítmica . [3]
Separaciones
En 1984, Furst, Saxe y Sipser demostraron que el cálculo de la paridad de una entrada no puede decidirse por ningún circuito AC 0 , incluso con falta de uniformidad. [4] [1] Se deduce que AC 0 no es igual a NC 1 , porque una familia de circuitos en la última clase puede calcular la paridad. [1] Se obtienen límites más precisos al cambiar de lema . Utilizándolos, se ha demostrado que existe una separación de oráculo entre la jerarquía polinomial y PSPACE .
Referencias
- ^ a b c d Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional. Un enfoque moderno . Prensa de la Universidad de Cambridge . pp. 117 -118, 287. ISBN 978-0-521-42426-4. Zbl 1193.68112 .
- ^ Barrington, David Mix; Maciel, Alexis (18 de julio de 2000). "Conferencia 2: La complejidad de algunos problemas" (PDF) . IAS / PCMI Sesión de verano 2000, Programa de pregrado de Clay Mathematics: Curso Básico de Complejidad Computacional .
- ^ Immerman, N. (1999). Complejidad descriptiva . Saltador. pag. 85 .
- ^ Furst, Merrick; Saxe, James B .; Sipser, Michael (1984). "Paridad, circuitos y jerarquía polinomial-temporal". Teoría de sistemas matemáticos . 17 (1): 13-27. doi : 10.1007 / BF01744431 . Señor 0738749 . Zbl 0534.94008 .