Complejidad del circuito

En informática teórica , la complejidad de 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. Un concepto relacionado es la complejidad de circuitos de un lenguaje recursivo , que se define mediante una familia uniforme de circuitos.${\displaystyle C_{1},C_{2},\ldots }$(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/poly consiste en funciones booleanas computables por circuitos de tamaño polinomial. Demostrar que${\displaystyle {\mathsf {NP}}\not \subseteq {\mathsf {P/poly}}}$separaría P y NP (ver más abajo).

Las clases de complejidad definidas en términos de circuitos booleanos incluyen AC ⁰ , AC , TC ⁰ , NC ¹ , NC , y P/poly .

Un circuito booleano con${\displaystyle n}$Los bits de entrada son un grafo dirigido acíclico en el que cada nodo (generalmente llamado compuerta en este contexto) es un nodo de entrada de grado 0 etiquetado por uno de los${\displaystyle n}$bits de entrada, una puerta AND , una puerta OR o una puerta NOT. Una de estas puertas se designa como la puerta de salida. Dicho circuito calcula naturalmente una función de sus bits de entrada, una puerta AND, una puerta OR o una puerta NOT . Una de estas puertas se designa como la puerta de salida. Dicho circuito calcula naturalmente una función de sus bits de entrada.${\displaystyle n}$entradas. El tamaño de un circuito es el número de compuertas que contiene y su profundidad es la longitud máxima de un camino desde una compuerta de entrada hasta la compuerta de salida.

Existen dos nociones principales de complejidad de circuitos. ^{[ 1 ]} La complejidad del tamaño del circuito de una función booleana${\displaystyle f}$es el tamaño mínimo de cualquier circuito computacional${\displaystyle f}$La complejidad de profundidad de circuito de una función booleana${\displaystyle f}$es la profundidad mínima de cualquier cálculo de circuitos${\displaystyle f}$.

Estas nociones se generalizan cuando se considera la complejidad de circuitos de cualquier lenguaje formal que contenga cadenas con diferentes longitudes de bits, especialmente lenguajes infinitos. Sin embargo, los circuitos booleanos solo permiten un número fijo de bits de entrada. Por lo tanto, ningún circuito booleano individual es capaz de decidir un lenguaje de este tipo. Para tener en cuenta esta posibilidad, se consideran familias de circuitos.${\displaystyle C_{1},C_{2},\ldots }$donde cada${\displaystyle C_{n}}$acepta entradas de tamaño${\displaystyle n}$Cada familia de circuitos generará naturalmente el lenguaje por circuito.${\displaystyle C_{n}}$salida${\displaystyle 1}$cuando una longitud${\displaystyle n}$La cuerda es un miembro de la familia, y${\displaystyle 0}$De lo contrario, decimos que una familia de circuitos es de tamaño mínimo si no hay otra familia que decida sobre entradas de cualquier tamaño.${\displaystyle n}$, con un circuito de menor tamaño que${\displaystyle C_{n}}$(respectivamente para familias de profundidad mínima ). Por lo tanto, la complejidad de circuitos es significativa incluso para lenguajes no recursivos . La noción de una familia uniforme permite relacionar variantes de la complejidad de circuitos con medidas de complejidad basadas en algoritmos para lenguajes recursivos. Sin embargo, la variante no uniforme resulta útil para encontrar límites inferiores sobre la complejidad que debe tener cualquier familia de circuitos para determinar la idoneidad de determinados lenguajes.

Por lo tanto, la complejidad del tamaño del circuito de un lenguaje formal${\displaystyle A}$se define como la función${\displaystyle t:\mathbb {N} \to \mathbb {N} }$, que relaciona la longitud en bits de una entrada,${\displaystyle n}$, a la complejidad del tamaño del circuito de un circuito mínimo${\displaystyle C_{n}}$que decide si las entradas de esa longitud están en${\displaystyle A}$La complejidad de la profundidad del circuito se define de manera similar.

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 distinta longitud son procesadas por circuitos diferentes, a diferencia de los modelos uniformes como las máquinas de Turing, donde se utiliza el mismo dispositivo computacional para todas las posibles longitudes de entrada. Por lo tanto, un problema computacional individual se asocia con una familia particular de circuitos booleanos.${\displaystyle C_{1},C_{2},\dots }$donde cada${\displaystyle C_{n}}$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 en recursos que, en la entrada n , produce una descripción del circuito individual.${\displaystyle C_{n}}$Cuando esta máquina de Turing tiene un tiempo de ejecución polinomial en n , se dice que la familia de circuitos es P-uniforme. El requisito más estricto de uniformidad DLOGTIME es de particular interés en el estudio de clases de circuitos de poca profundidad, como AC ⁰ 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.

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 ). A pesar de esto, los teóricos de la complejidad no han podido demostrar hasta ahora una cota inferior superlineal para ninguna función explícita.

Se han demostrado cotas inferiores superpolinomiales bajo ciertas restricciones en la familia de circuitos utilizados. La primera función para la que se mostraron cotas inferiores de circuito superpolinomiales 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 ⁰ fue establecido por primera vez independientemente por Ajtai en 1983 ^{[ 3 ] [ 4 ]} y por Furst, Saxe y Sipser en 1984. ^{[ 5 ]} Mejoras posteriores de Håstad en 1987 ^{[ 6 ]} establecieron que cualquier familia de circuitos de profundidad constante que calculen la función de paridad requiere un tamaño exponencial. Extendiendo un resultado de Razborov , ^{[ 7 ]} Smolensky en 1987 ^{[ 8 ]} demostró que esto es cierto incluso si el circuito se aumenta con puertas que calculan la suma de sus bits de entrada módulo algún primo impar p .

El problema de la k -clique consiste en decidir si un grafo dado con n vértices tiene una clique de tamaño k . Para cualquier elección particular de las constantes n y k , el grafo se puede codificar en binario utilizando${\displaystyle {n \choose 2}}$bits, que indican para cada posible arista si está presente. Luego, el problema de la k -clique se formaliza como una función${\displaystyle f_{k}:\{0,1\}^{n \choose 2}\to \{0,1\}}$de tal manera que${\displaystyle f_{k}}$produce 1 si y solo si el grafo 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 polinomial (es decir, circuitos con puertas AND y OR pero sin negación). El resultado original de Razborov en 1985 ^{[ 7 ]} fue mejorado posteriormente a una cota inferior de tamaño exponencial por Alon y Boppana en 1987. ^{[ 9 ]} En 2008, Rossman ^{[ 10 ]} demostró que los circuitos de profundidad constante con puertas AND, OR y NOT requieren tamaño${\displaystyle \Omega (n^{k/4})}$para resolver el problema de la k -clique incluso en el caso promedio . Además, existe un circuito de tamaño${\displaystyle n^{k/4+O(1)}}$que calcula${\displaystyle f_{k}}$.

En 1999, Raz y McKenzie demostraron posteriormente que la jerarquía NC monótona es infinita. ^{[ 11 ]}

El problema de la división entera se encuentra en TC uniforme ⁰ . ^{[ 12 ]}

Los límites inferiores de los circuitos son generalmente difíciles de determinar. Los resultados conocidos incluyen:

• La paridad no está en AC ⁰ no uniforme , demostrado por Ajtai en 1983 ^{[ 3 ] [ 4 ]} así como por Furst, Saxe y Sipser en 1984. ^{[ 5 ]}
• El TC uniforme ⁰ está estrictamente contenido en PP , probado por Allender . ^{[ 13 ]}
• Las clases O ^P ₂ , ^{[ 14 ]} PP ^{[ nb 1 ]} y MA /1 ^{[ 15 ]} (MA con un poco de consejo) no están en SIZE ( n ^k ) para ninguna constante k.
• Si bien se sospecha que la clase no uniforme ACC ⁰ no contiene la función mayoritaria, fue solo en 2010 que Williams demostró que${\displaystyle {\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}}$. ^{[ 16 ]}

Queda por determinar si NEXPTIME tiene circuitos TC ^{0 no uniformes.}

Las demostraciones de límites inferiores de circuitos están fuertemente conectadas con la desaleatorización . Una demostración de que${\displaystyle {\mathsf {P}}={\mathsf {BPP}}}$implicaría que o${\displaystyle {\mathsf {NEXP}}\not \subseteq {\mathsf {P/poly}}}$o que el permanente de una matriz no se puede calcular mediante circuitos aritméticos no uniformes (polinomios) de tamaño y grado polinomial. ^{[ 17 ]}

En 1997, Razborov y Rudich demostraron que muchas cotas inferiores de circuitos conocidas para funciones booleanas explícitas implican la existencia de las llamadas propiedades naturales útiles contra la clase de circuito correspondiente. ^{[ 18 ]} Por otro lado, las propiedades naturales útiles contra P/poly romperían los generadores pseudoaleatorios fuertes. Esto se interpreta a menudo como una barrera de "pruebas naturales" para demostrar cotas inferiores de circuitos fuertes. En 2016, Carmosino, Impagliazzo, Kabanets y Kolokolova demostraron que las propiedades naturales también pueden usarse para construir algoritmos de aprendizaje eficientes. ^{[ 19 ]}

Muchas clases de complejidad de circuitos se definen en términos de jerarquías de clases. Para cada entero no negativo i , existe una clase NC ⁱ , que consta de circuitos de tamaño polinomial de profundidad${\displaystyle O(\log ^{i}(n))}$, utilizando compuertas AND, OR y NOT con entrada limitada . La unión NC de todas estas clases es objeto de estudio. Al considerar compuertas con entrada ilimitada, se pueden construir las clases AC ⁱ 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 compuertas.

Si un determinado idioma,${\displaystyle A}$pertenece a la clase de complejidad temporal${\displaystyle {\text{TIEMPO}}(t(n))}$para alguna función${\displaystyle t:\mathbb {N} \to \mathbb {N} }$, entonces${\displaystyle A}$tiene complejidad de circuito${\displaystyle {\mathcal {O}}(t(n)\log t(n))}$Si la máquina de Turing que acepta el lenguaje es ajena a la información (es decir, lee y escribe en las mismas celdas de memoria independientemente de la entrada), entonces${\displaystyle A}$tiene complejidad de circuito${\displaystyle {\mathcal {O}}(t(n))}$. ^{[ 20 ]}

Un circuito booleano monótono es aquel que solo tiene compuertas AND y OR, pero no compuertas NOT. Un circuito monótono solo puede calcular una función booleana monótona, que es una función${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$donde para cada${\displaystyle x,y\in \{0,1\}^{n}}$,${\displaystyle x\leq y\implies f(x)\leq f(y)}$, dónde${\displaystyle x\leq y}$significa que${\displaystyle x_{i}\leq y_{i}}$a pesar de${\displaystyle i\in \{1,\ldots ,n\}}$.

• Minimización de circuitos

• Vollmer, Heribert [en alemán] (1999). Introducción a la complejidad de circuitos: un enfoque uniforme . Textos en informática teórica. 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. Frankfurt am Main/Bielefeld, Alemania: John Wiley & Sons Ltd. y BG Teubner Verlag , Stuttgart. ISBN 3-519-02107-2. LCCN 87-10388 . (xii+457 páginas) (Nota: En su momento, fue un influyente libro de texto sobre el tema, conocido comúnmente como el "Libro Azul". También disponible para su descarga (PDF) en el Coloquio Electrónico sobre Complejidad Computacional ).
• Zwick, Uri . "Apuntes de clase para un curso de Uri Zwick sobre complejidad de circuitos" .