En la informática teórica , la complejidad de los circuitos es una rama de la teoría de la complejidad computacional en la que las funciones booleanas se clasifican según el tamaño o la profundidad de los circuitos booleanos que las calculan. Una noción relacionada es la complejidad del circuito de un lenguaje recursivo que es decidido por una familia uniforme de circuitos. (vea abajo).
Demostrar límites inferiores en el tamaño de los circuitos booleanos que calculan funciones booleanas explícitas es un enfoque popular para separar clases de complejidad. Por ejemplo, una clase de circuito prominente P / poli consta de funciones booleanas calculables por circuitos de tamaño polinómico. Demostrando quesepararía P y NP (ver más abajo).
Las clases de complejidad definidas en términos de circuitos booleanos incluyen AC 0 , AC , TC 0 , NC 1 , NC y P / poly .
Tamaño y profundidad
Un circuito booleano con Los bits de entrada son un gráfico acíclico dirigido en el que cada nodo (generalmente llamado puertas en este contexto) es un nodo de entrada de grado 0 etiquetado por uno de losbits de entrada, una puerta Y , una puerta O o una puerta NO . Una de estas puertas se designa como puerta de salida. Tal circuito calcula naturalmente una función de suentradas. El tamaño de un circuito es el número de puertas que contiene y su profundidad es la longitud máxima de una ruta desde una puerta de entrada a la puerta de salida.
Hay dos nociones principales de complejidad de circuito [1] La complejidad del tamaño de circuito de una función booleana es el tamaño mínimo de cualquier circuito informático . La complejidad de la profundidad del circuito de una función booleana es la profundidad mínima de cualquier circuito informático .
Estas nociones se generalizan cuando se considera la complejidad del circuito de cualquier lenguaje que contenga cadenas con diferentes longitudes de bits, especialmente lenguajes formales infinitos . Los circuitos booleanos, sin embargo, solo permiten un número fijo de bits de entrada. Por lo tanto, ningún circuito booleano es capaz de decidir ese idioma. Para tener en cuenta esta posibilidad, se consideran familias de circuitos donde cada acepta entradas de tamaño . Cada familia de circuitos generará naturalmente el lenguaje por circuito. dando salida cuando una longitud string es un miembro de la familia, y de lo contrario. Decimos que una familia de circuitos tiene un tamaño mínimo si no hay otra familia que decida sobre entradas de cualquier tamaño,, con un circuito de menor tamaño que (respectivamente para familias de profundidad mínima ). Por lo tanto, la complejidad del circuito es significativa incluso para lenguajes no recursivos . La noción de una familia uniforme permite que las variantes de la complejidad del circuito se relacionen con las medidas de complejidad basadas en algoritmos de los lenguajes recursivos. Sin embargo, la variante no uniforme es útil para encontrar límites inferiores sobre cuán compleja debe ser cualquier familia de circuitos para decidir idiomas dados.
Por tanto, la complejidad del tamaño de un circuito de un lenguaje formal se define como la función , que relaciona una longitud de bits de una entrada, , a la complejidad del tamaño del circuito de un circuito mínimo que decide si las entradas de esa longitud están en . La complejidad de la profundidad del circuito se define de manera similar.
Uniformidad
Los circuitos booleanos son uno de los principales ejemplos de los llamados modelos de computación no uniformes en el sentido de que las entradas de diferentes longitudes son procesadas por diferentes circuitos, en contraste con modelos uniformes como las máquinas de Turing donde se usa el mismo dispositivo computacional para todos. posibles longitudes de entrada. Por tanto, un problema de cálculo individual se asocia con una familia particular de circuitos booleanos donde cada es el circuito que maneja entradas de n bits. A menudo se impone una condición de uniformidad a estas familias, que requiere la existencia de alguna máquina de Turing posiblemente limitada por recursos que, en la entrada n , produce una descripción del circuito individual.. Cuando esta máquina de Turing tiene un polinomio de tiempo de funcionamiento en n , se dice que la familia de circuitos es P-uniforme. El requisito más estricto de la uniformidad DLOGTIME es de particular interés en el estudio de clases de circuitos de poca profundidad como AC 0 o TC 0 . Cuando no se especifican límites de recursos, un lenguaje es recursivo (es decir, decidible por una máquina de Turing) si y solo si el lenguaje es decidido por una familia uniforme de circuitos booleanos.
Uniforme de tiempo polinomial
Una familia de circuitos booleanos es uniforme en tiempo polinomial si existe una máquina de Turing determinista M , tal que
- M corre en tiempo polinomial
- Para todos , M genera una descripción de en la entrada
Uniforme de espacio de troncos
Una familia de circuitos booleanos ¿Es el espacio logarítmico uniforme si existe una máquina de Turing determinista M , tal que
- M corre en el espacio logarítmico
- Para todos , M genera una descripción de en la entrada
Historia
La complejidad de los circuitos se remonta a Shannon en 1949, [2] quien demostró que casi todas las funciones booleanas en n variables requieren circuitos de tamaño Θ (2 n / n ). A pesar de este hecho, los teóricos de la complejidad solo han podido probar los límites inferiores del circuito superpolinómico en funciones construidas explícitamente con el propósito de ser difíciles de calcular.
Más comúnmente, los límites inferiores superpolinomiales se han probado bajo ciertas restricciones en la familia de circuitos utilizados. La primera función para la que se mostraron los límites inferiores del circuito superpolinomial fue la función de paridad , que calcula la suma de sus bits de entrada módulo 2. El hecho de que la paridad no esté contenida en AC 0 fue establecido por primera vez de forma independiente por Ajtai en 1983 [3] [4 ] y Furst, Saxe y Sipser en 1984. [5] Las mejoras posteriores de Håstad en 1987 [6] establecieron que cualquier familia de circuitos de profundidad constante que calculan la función de paridad requiere un tamaño exponencial. Ampliando un resultado de Razborov, [7] Smolensky en 1987 [8] demostró que esto es cierto incluso si el circuito se aumenta con compuertas que calculan la suma de sus bits de entrada módulo algún primo impar p .
El problema de k -clique es decidir si un gráfico dado en n vértices tiene un clique de tamaño k . Para cualquier elección particular de las constantes n y k , el gráfico se puede codificar en binario usandobits, que indican para cada posible borde si está presente. Entonces el problema de k -clique se formaliza como una función tal que salidas 1 si y solo si el gráfico codificado por la cadena contiene una camarilla de tamaño k . Esta familia de funciones es monótona y puede ser calculada por una familia de circuitos, pero se ha demostrado que no puede ser calculada por una familia de circuitos monótonos de tamaño polinómico (es decir, circuitos con puertas Y y O pero sin negación). El resultado original de Razborov en 1985 [7] fue posteriormente mejorado a un límite inferior de tamaño exponencial por Alon y Boppana en 1987. [9] En 2008, Rossman [10] mostró que los circuitos de profundidad constante con Y, O y NO las puertas requieren tamañopara resolver el problema de k -clique incluso en el caso medio . Además, hay un circuito de tamaño que computa .
En 1999, Raz y McKenzie demostraron más tarde que la jerarquía monótona de NC es infinita. [11]
El problema de la división de enteros radica en TC 0 uniforme . [12]
Límites inferiores del circuito
Los límites inferiores del circuito son generalmente difíciles. Los resultados conocidos incluyen
- La paridad no está en AC 0 no uniforme , probado por Ajtai en 1983 [3] [4] así como por Furst, Saxe y Sipser en 1984. [5]
- Uniform TC 0 está estrictamente contenido en PP , probado por Allender. [13]
- Las clases SP 2, PP [nb 1] y MA / 1 [14] (MA con un bit de aviso) no están en SIZE (n k ) para cualquier constante k.
- Si bien se sospecha que la clase no uniforme ACC 0 no contiene la función mayoritaria, solo en 2010 Williams demostró que. [15]
Está abierto si NEXPTIME tiene circuitos TC 0 no uniformes .
Las pruebas de los límites inferiores del circuito están fuertemente conectadas a la desaleatorización . Una prueba de que implicaría que o o ese permanente no puede ser calculado por circuitos aritméticos no uniformes (polinomios) de tamaño polinomial y grado polinomial. [dieciséis]
En 1997, Razborov y Rudich demostraron que muchos límites inferiores de circuitos conocidos para funciones booleanas explícitas implican la existencia de las llamadas propiedades naturales útiles contra la clase de circuito respectiva. [17] Por otro lado, las propiedades naturales útiles contra P / poly romperían generadores pseudoaleatorios fuertes. Esto a menudo se interpreta como una barrera de "pruebas naturales" para demostrar límites inferiores de circuito fuertes. En 2016, Carmosino, Impagliazzo, Kabanets y Kolokolova demostraron que las propiedades naturales también se pueden utilizar para construir algoritmos de aprendizaje eficientes. [18]
Clases de complejidad
Muchas clases de complejidad de circuitos se definen en términos de jerarquías de clases. Para cada entero no negativo i , hay una clase NC i , que consta de circuitos de profundidad de tamaño polinómico, utilizando compuertas Y, O y NO en abanico delimitadas. La unión NC de todas estas clases es un tema de discusión. Al considerar puertas de entrada de abanico ilimitadas, se pueden construir las clases AC i y AC (que es igual a NC). Se pueden construir muchas otras clases de complejidad de circuitos con las mismas restricciones de tamaño y profundidad permitiendo diferentes conjuntos de puertas.
Relación con la complejidad del tiempo
Si un idioma determinado, , pertenece a la clase de complejidad temporal para alguna función , luego tiene complejidad de circuito . [1]
Ver también
- Minimización de circuitos
Notas
- ^ Ver prueba .
Referencias
- ↑ a b Sipser, Michael (1997). Introducción a la teoría de la computación (1 ed.). Boston, Estados Unidos: PWS Publishing Company. pag. 324.
- ^ Shannon, Claude Elwood (1949). "La síntesis de circuitos de conmutación de dos terminales". Revista técnica de Bell System . 28 (1): 59–98. doi : 10.1002 / j.1538-7305.1949.tb03624.x .
- ^ a b Ajtai, Miklós (1983). "-formulas sobre estructuras finitas ". Annals of Pure and Applied Logic . 24 : 1–24. doi : 10.1016 / 0168-0072 (83) 90038-6 .
- ^ a b Ajtai, Miklós ; Komlós, János; Szemerédi, Endre (1983). Una red de clasificación 0 (n log n) . STOC '83 Actas del Decimoquinto Simposio Anual ACM sobre Teoría de la Computación . págs. 1–9. ISBN 978-0-89791-099-6.
- ^ a b Furst, Merrick L .; Saxe, James Benjamin ; Sipser, Michael Fredric (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 .
- ^ Håstad, Johan Torkel (1987). Limitaciones computacionales de circuitos de pequeña profundidad (PDF) (tesis doctoral). Instituto de Tecnología de Massachusetts.
- ^ a b Razborov, Aleksandr Aleksandrovich (1985). "Límites inferiores de la complejidad monótona de algunas funciones booleanas". Matemáticas soviéticas - Doklady . 31 : 354–357. ISSN 0197-6788 .
- ^ Smolensky, Roman (1987). "Métodos algebraicos en la teoría de límites inferiores para la complejidad del circuito booleano". Actas del XIX Simposio Anual ACM sobre Teoría de la Computación . Asociación de Maquinaria Informática . págs. 77–82. doi : 10.1145 / 28395.28404 .
- ^ Alon, Noga ; Boppana, Ravi B. (1987). "La complejidad del circuito monótono de las funciones booleanas". Combinatorica . 7 (1): 1–22. CiteSeerX 10.1.1.300.9623 . doi : 10.1007 / bf02579196 .
- ^ Rossman, Benjamin E. (2008). "Sobre la complejidad de profundidad constante de k-clique". STOC 2008: Actas del 40º simposio anual de ACM sobre teoría de la computación . Asociación de Maquinaria Informática . págs. 721–730. doi : 10.1145 / 1374376.1374480 .
- ^ Raz, Ran ; McKenzie, Pierre (1999). "Separación de la jerarquía NC monótona". Combinatorica . 19 (3): 403–435. doi : 10.1007 / s004930050062 .
- ^ Hesse, William (2001). "La división es uniforme TC 0 ". Actas del 28º Coloquio Internacional sobre Autómatas, Lenguajes y Programación . Springer Verlag . págs. 104-114.
- ^ Allender, Eric Warren , ed. (1997). "Complejidad del circuito antes del amanecer del nuevo milenio" (PDF) . [1] (NB. Un estudio de campo realizado en 1997 por Eric Allender).
- ^ Santhanam, Rahul (2007). "Límites inferiores del circuito para las clases Merlin-Arthur" . STOC 2007: Actas del trigésimo noveno simposio anual de ACM sobre teoría de la computación . págs. 275-283. CiteSeerX 10.1.1.92.4422 . doi : 10.1145 / 1250790.1250832 .
- ^ Williams, Richard Ryan (2011). "Límites inferiores del circuito ACC no uniforme" (PDF) . CCC 2011: Actas de la 26ª Conferencia Anual del IEEE sobre Complejidad Computacional . págs. 115-125. doi : 10.1109 / CCC.2011.36 .
- ^ Kabanets, Valentine ; Impagliazzo, Russell Graham (2004). "Desaleatorizar las pruebas de identidad polinomial significa probar los límites inferiores del circuito". Complejidad computacional . 13 (1): 1–46. doi : 10.1007 / s00037-004-0182-6 .
- ^ Razborov, Aleksandr Aleksandrovich ; Rudich, Steven (1997). "Pruebas naturales". Revista de Ciencias de la Computación y Sistemas . 55 . págs. 24–35.
- ^ Carmosino, Marco; Impagliazzo, Russell Graham ; Kabanets, Valentine ; Kolokolova, Antonina (2016). "Aprendizaje de algoritmos a partir de pruebas naturales". Conferencia de Complejidad Computacional .
Otras lecturas
- Vollmer, Heribert (1999). Introducción a la complejidad de los circuitos: un enfoque uniforme . Textos en Informática Teórica. Una serie EATCS. Springer Verlag . ISBN 978-3-540-64310-4.
- Wegener, Ingo (1987) [noviembre de 1986]. La complejidad de las funciones booleanas . Serie Wiley-Teubner en Ciencias de la Computación. Fráncfort del Meno / Bielefeld, Alemania: John Wiley & Sons Ltd. y BG Teubner Verlag , Stuttgart. ISBN 3-519-02107-2. LCCN 87-10388 .(xii + 457 páginas) (NB. En ese momento, un influyente libro de texto sobre el tema, comúnmente conocido como el "Libro Azul". También disponible para descargar (PDF) en el Coloquio Electrónico sobre Complejidad Computacional .)
- Zwick, Uri . "Apuntes de clase para un curso de Uri Zwick sobre complejidad de circuitos" .