Complejidad de circuitos aritméticos

En la teoría de la complejidad computacional , los circuitos aritméticos son el modelo estándar para calcular polinomios . De manera informal, un circuito aritmético toma como entradas variables o números, y puede sumar o multiplicar dos expresiones que ya ha calculado. Los circuitos aritméticos proporcionan una forma formal de entender la complejidad del cálculo de polinomios. El tipo básico de pregunta en esta línea de investigación es "¿cuál es la forma más eficiente de calcular un polinomio dado ?". ${\displaystyle f}$

Definiciones

Un circuito aritmético simple.

Un circuito aritmético sobre el campo y el conjunto de variables es un grafo acíclico dirigido como sigue. Cada nodo en él con grado de entrada cero se llama puerta de entrada y está etiquetado por una variable o un elemento de campo en Cada otra puerta está etiquetada por o en el primer caso es una puerta de suma y en el segundo una puerta de producto . Una fórmula aritmética es un circuito en el que cada puerta tiene grado de salida uno (y por lo tanto el grafo subyacente es un árbol dirigido ). ${\displaystyle C}$ ${\displaystyle F}$ ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle x_{i}}$ ${\displaystyle F.}$ ${\displaystyle +}$ ${\displaystyle \times ;}$

Un circuito tiene dos medidas de complejidad asociadas: tamaño y profundidad. El tamaño de un circuito es la cantidad de puertas que tiene y la profundidad es la longitud de la ruta dirigida más larga que tiene. Por ejemplo, el circuito de la figura tiene un tamaño de seis y una profundidad de dos.

Un circuito aritmético calcula un polinomio de la siguiente manera natural. Una compuerta de entrada calcula el polinomio que lo etiqueta. Una compuerta de suma calcula la suma de los polinomios calculados por sus hijos (una compuerta es hija de si la arista dirigida está en el gráfico). Una compuerta de producto calcula el producto de los polinomios calculados por sus hijos. Considere el circuito de la figura, por ejemplo: las compuertas de entrada calculan (de izquierda a derecha) y las compuertas de suma calculan y y la compuerta de producto calcula ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle (v,u)}$ ${\displaystyle x_{1},x_{2}}$ ${\displaystyle 1,}$ ${\displaystyle x_{1}+x_{2}}$ ${\displaystyle x_{2}+1,}$ ${\displaystyle (x_{1}+x_{2})x_{2}(x_{2}+1).}$

Descripción general

Dado un polinomio, podemos preguntarnos cuál es la mejor manera de calcularlo; por ejemplo, ¿cuál es el tamaño más pequeño de un circuito que calcula? La respuesta a esta pregunta consta de dos partes. La primera parte es encontrar un circuito que calcule esta parte, que generalmente se llama acotación superior de la complejidad de La segunda parte es demostrar que ningún otro circuito puede hacerlo mejor; esta parte se llama acotación inferior de la complejidad de Aunque estas dos tareas están fuertemente relacionadas, demostrar cotas inferiores suele ser más difícil, ya que para demostrar una cota inferior es necesario discutir sobre todos los circuitos al mismo tiempo. ${\displaystyle f,}$ ${\displaystyle f.}$ ${\displaystyle f;}$ ${\displaystyle f.}$ ${\displaystyle f.}$

Nótese que estamos interesados ​​en el cálculo formal de polinomios, más que en las funciones que los polinomios definen. Por ejemplo, considere el polinomio sobre el campo de dos elementos: este polinomio representa la función cero, pero no es el polinomio cero. Esta es una de las diferencias entre el estudio de circuitos aritméticos y el estudio de circuitos booleanos . En la complejidad booleana, uno está principalmente interesado en calcular una función, más que alguna representación de ella (en nuestro caso, una representación por un polinomio). Esta es una de las razones que hacen que la complejidad booleana sea más difícil que la complejidad aritmética. El estudio de circuitos aritméticos también puede considerarse como uno de los pasos intermedios hacia el estudio del caso booleano, ^[1] que apenas entendemos. ${\displaystyle x^{2}+x;}$

Límites superiores

Como parte del estudio de la complejidad del cálculo de polinomios, se encontraron algunos circuitos ingeniosos (algoritmos alternativos). Un ejemplo bien conocido es el algoritmo de Strassen para el producto de matrices . La forma sencilla de calcular el producto de dos matrices requiere un circuito de tamaño del orden de Strassen demostró que, de hecho, podemos multiplicar dos matrices utilizando un circuito de tamaño aproximado . La idea básica de Strassen es una forma inteligente de multiplicar matrices. Esta idea es el punto de partida de la mejor forma teórica de multiplicar dos matrices que lleva tiempo aproximadamente. ${\displaystyle n\times n}$ ${\displaystyle n^{3}.}$ ${\displaystyle n^{2.807}.}$ ${\displaystyle 2\times 2}$ ${\displaystyle n^{2.376}.}$

Otra historia interesante se esconde detrás del cálculo del determinante de una matriz. La forma ingenua de calcular el determinante requiere circuitos de tamaño aproximadamente igual a 100. Sin embargo, sabemos que existen circuitos de tamaño polinómico en para calcular el determinante. Estos circuitos, sin embargo, tienen una profundidad que es lineal en 100. Berkowitz propuso una mejora: un circuito de tamaño polinómico en 100 pero de profundidad ^[2]. ${\displaystyle n\times n}$ ${\displaystyle n!.}$ ${\displaystyle n}$ ${\displaystyle n.}$ ${\displaystyle n,}$ ${\displaystyle O(\log ^{2}(n)).}$

También nos gustaría mencionar el mejor circuito conocido para la permanente de una matriz. En cuanto al determinante, el circuito ingenuo para la permanente tiene un tamaño aproximado. Sin embargo, para la permanente, el mejor circuito conocido tiene un tamaño aproximado que viene dado por la fórmula de Ryser: para una matriz ${\displaystyle n\times n}$ ${\displaystyle n!.}$ ${\displaystyle 2^{n},}$ ${\displaystyle n\times n}$ ${\displaystyle X=(x_{i,j}),}$

${\displaystyle \operatorname {perm} (X)=(-1)^{n}\sum _{S\subseteq \{1,\ldots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}x_{i,j}}$

(este es un circuito de profundidad tres).

Límites inferiores

En términos de probar límites inferiores, nuestro conocimiento es muy limitado. Dado que estudiamos el cálculo de polinomios formales, sabemos que los polinomios de grado muy grande requieren circuitos grandes, por ejemplo, un polinomio de grado requiere un circuito de tamaño aproximadamente Entonces, el objetivo principal es probar el límite inferior para polinomios de grado pequeño, digamos, polinomio en De hecho, como en muchas áreas de las matemáticas, los argumentos de conteo nos dicen que hay polinomios de grado polinomial que requieren circuitos de tamaño superpolinomial. Sin embargo, estos argumentos de conteo generalmente no mejoran nuestra comprensión del cálculo. El siguiente problema es el principal problema abierto en esta área de investigación: encontrar un polinomio explícito de grado polinomial que requiera circuitos de tamaño superpolinomial . ${\displaystyle 2^{2^{n}}}$ ${\displaystyle 2^{n}.}$ ${\displaystyle n.}$

El estado del arte es un límite inferior para el tamaño de un circuito que calcula, por ejemplo, el polinomio dado por Strassen y por Baur y Strassen. Más precisamente, Strassen utilizó el teorema de Bézout para mostrar que cualquier circuito que calcule simultáneamente los polinomios es de tamaño y más tarde Baur y Strassen mostraron lo siguiente: dado un circuito aritmético de tamaño que calcula un polinomio, se puede construir un nuevo circuito de tamaño como máximo que calcule y todas las derivadas parciales de Dado que las derivadas parciales de son el límite inferior de Strassen también se aplica a. ^[3] Este es un ejemplo donde algún límite superior ayuda a demostrar límites inferiores; la construcción de un circuito dado por Baur y Strassen implica un límite inferior para polinomios más generales. ${\displaystyle \Omega (n\log d)}$ ${\displaystyle x_{1}^{d}+\cdots +x_{n}^{d}}$ ${\displaystyle n}$ ${\displaystyle x_{1}^{d},\ldots ,x_{n}^{d}}$ ${\displaystyle \Omega (n\log d),}$ ${\displaystyle s}$ ${\displaystyle f,}$ ${\displaystyle O(s)}$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle f.}$ ${\displaystyle x_{1}^{d}+\cdots +x_{n}^{d}}$ ${\displaystyle dx_{1}^{d-1},\ldots ,dx_{n}^{d-1},}$ ${\displaystyle x_{1}^{d}+\cdots +x_{n}^{d}}$

La falta de capacidad para demostrar límites inferiores nos lleva a considerar modelos de cálculo más simples. Algunos ejemplos son: circuitos monótonos (en los que todos los elementos del campo son números reales no negativos), circuitos de profundidad constante y circuitos multilineales (en los que cada compuerta calcula un polinomio multilineal ). Estos modelos restringidos se han estudiado ampliamente y se han obtenido algunos conocimientos y resultados.

P y NP algebraicos

El problema abierto más interesante en la teoría de la complejidad computacional es el problema P vs. NP . En términos generales, este problema consiste en determinar si un problema dado se puede resolver con la misma facilidad con la que se puede demostrar que existe una solución para el problema dado. En su obra seminal, Valiant ^[4] sugirió un análogo algebraico de este problema, el problema VP vs. VNP .

La clase VP es el análogo algebraico de P; es la clase de polinomios de grado polinomial que tienen circuitos de tamaño polinomial sobre un campo fijo . La clase VNP es el análogo de NP. VNP puede considerarse como la clase de polinomios de grado polinomial tal que dado un monomio podemos determinar su coeficiente de manera eficiente, con un circuito de tamaño polinomial. ${\displaystyle f}$ ${\displaystyle K.}$ ${\displaystyle f}$ ${\displaystyle f}$

Una de las nociones básicas en la teoría de la complejidad es la noción de completitud . Dada una clase de polinomios (como VP o VNP), un polinomio completo para esta clase es un polinomio con dos propiedades: (1) es parte de la clase, y (2) cualquier otro polinomio en la clase es más fácil que en el sentido de que si tiene un circuito pequeño entonces también lo tiene Valiant demostró que el permanente es completo para la clase VNP. Entonces, para demostrar que VP no es igual a VNP, uno necesita demostrar que el permanente no tiene circuitos de tamaño polinomial. Este sigue siendo un problema abierto pendiente. ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f,}$ ${\displaystyle f}$ ${\displaystyle g.}$

Reducción de profundidad

Un punto de referencia en nuestra comprensión del cálculo de polinomios es el trabajo de Valiant, Skyum, Berkowitz y Rackoff. ^[5] Demostraron que si un polinomio de grado tiene un circuito de tamaño entonces también tiene un circuito de tamaño polinomial en y de profundidad Por ejemplo, cualquier polinomio de grado que tenga un circuito de tamaño polinomial, también tiene un circuito de tamaño polinomial de profundidad aproximadamente Este resultado generaliza el circuito de Berkowitz a cualquier polinomio de grado polinomial que tenga un circuito de tamaño polinomial (como el determinante). Se cree que el análogo de este resultado en el entorno booleano es falso. ${\displaystyle f}$ ${\displaystyle r}$ ${\displaystyle s,}$ ${\displaystyle f}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle O(\log(r)\log(s)).}$ ${\displaystyle n}$ ${\displaystyle \log ^{2}(n).}$

Un corolario de este resultado es una simulación de circuitos mediante fórmulas relativamente pequeñas, fórmulas de tamaño cuasipolinomial: si un polinomio de grado tiene un circuito de tamaño entonces tiene una fórmula de tamaño Esta simulación es más fácil que la reducción de profundidad de Valiant et al. y fue demostrada anteriormente por Hyafil. ^[6] ${\displaystyle f}$ ${\displaystyle r}$ ${\displaystyle s,}$ ${\displaystyle s^{O(\log(r))}.}$

Véase también

• Evaluación de polinomios para una discusión más general y menos formal de la complejidad de la evaluación de polinomios.

Lectura adicional

• Bürgisser, Peter (2000). Completitud y reducción en la teoría de la complejidad algebraica . Algoritmos y computación en matemáticas. Vol. 7. Berlín: Springer-Verlag . ISBN. 978-3-540-66752-0.Zbl 0948.68082  .
• Bürgisser, Peter; Clausen, Michael; Shokrollahi, M. Amin (1997). Teoría de la complejidad algebraica . Grundlehren der Mathematischen Wissenschaften. vol. 315. Con la colaboración de Thomas Lickteig. Berlín: Springer-Verlag . ISBN 978-3-540-60582-9.Zbl1087.68568  .​
• Von zur Gathen, Joachim (1988). "Teoría de la complejidad algebraica". Revisión anual de informática . 3 : 317–347. doi : 10.1146/annurev.cs.03.060188.001533.

Notas al pie

1. LG Valiant. ¿Por qué es difícil la teoría de la complejidad de Boole? Actas del simposio de la London Mathematical Society sobre la complejidad de las funciones de Boole, págs. 84-94, 1992.
2. SJ Berkowitz. Sobre el cálculo del determinante en tiempos paralelos pequeños utilizando un pequeño número de procesadores. Inf. Prod. Letters 18, págs. 147-150, 1984.
3. Shpilka, Amir; Yehudayoff, Amir (2010). "Circuitos aritméticos: un estudio de resultados recientes y preguntas abiertas" (PDF) . Fundamentos y tendencias en informática teórica . 5 (3–4): 207-388. doi :10.1561/0400000039.
4. Valiant, LG (1979). Clases de completitud en álgebra . ACM Press. doi :10.1145/800135.804419.
5. Valiant, LG; Skyum, S.; Berkowitz, S.; Rackoff, C. (1983). "Cálculo rápido en paralelo de polinomios utilizando pocos procesadores". Revista SIAM de informática . 12 (4): 641–644. doi :10.1137/0212043. ISSN  0097-5397.
6. Hyafil, Laurent (1979). "Sobre la evaluación paralela de polinomios multivariados". Revista SIAM de Computación . 8 (2): 120–123. doi :10.1137/0208010. ISSN  0097-5397.