Hispanopedia Wiki
Articulo de referencia

Complejidad de los circuitos aritméticos

En la teoría de la complejidad computacional , los circuitos aritméticos son el modelo estándar para el cálculo de polinomios . De manera informal, un circuito aritmético toma c...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de la complejidad computacional , los circuitos aritméticos son el modelo estándar para el cálculo de 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 comprender 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?".F{\displaystyle f}?"

Definiciones

Un circuito aritmético simple para calcular(incógnita1+incógnita2)incógnita2(incógnita2+1){\displaystyle (x_{1}+x_{2})x_{2}(x_{2}+1)}.

Un circuito aritméticodo{\displaystyle C}sobre el campoF{\displaystyle F}y el conjunto de variablesincógnita1,…,incógnitanorte{\displaystyle x_{1},\ldots ,x_{n}}es un grafo dirigido acíclico como sigue. Cada nodo en él con grado de entrada cero se llama puerta de entrada y está etiquetado por una variableincógnitai{\displaystyle x_{i}}o un elemento de campo enF.{\displaystyle F.}Cada una de las demás puertas está etiquetada por+{\displaystyle +}o×;{\displaystyle \times ;} en el primer caso es una puerta suma y en el segundo unapuerta 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 ).

Un circuito tiene dos medidas de complejidad asociadas: tamaño y profundidad. El tamaño de un circuito es el número de compuertas que contiene, y la profundidad es la longitud del camino dirigido más largo. 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 puerta de entrada calcula el polinomio con el que está etiquetada. Una puerta de sumav{\displaystyle v}calcula la suma de los polinomios calculados por sus hijos (una puertatú{\displaystyle u}es hijo dev{\displaystyle v}si el borde dirigido(v,tú){\displaystyle (v,u)}está en el gráfico). Una puerta de producto calcula el producto de los polinomios calculados por sus hijos. Considere el circuito de la figura, por ejemplo: las puertas de entrada calculan (de izquierda a derecha)incógnita1,incógnita2{\displaystyle x_{1},x_{2}}y1,{\displaystyle 1,}Las compuertas de suma calculanincógnita1+incógnita2{\displaystyle x_{1}+x_{2}}yincógnita2+1,{\displaystyle x_{2}+1,}y la puerta del producto calcula(incógnita1+incógnita2)incógnita2(incógnita2+1).{\displaystyle (x_{1}+x_{2})x_{2}(x_{2}+1).}

Descripción general

Dado un polinomioF,{\displaystyle f,}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 de cálculo?F.{\displaystyle f.}La respuesta a esta pregunta consta de dos partes. La primera parte consiste en encontrar algún circuito que calculeF;{\displaystyle f;}Esta parte se suele llamar límite superior de la complejidad deF.{\displaystyle f.}La segunda parte consiste en demostrar que ningún otro circuito puede hacerlo mejor; esta parte se denomina límite inferior de la complejidad de F.{\displaystyle f.}Aunque estas dos tareas están estrechamente relacionadas, demostrar cotas inferiores suele ser más difícil, ya que para demostrar una cota inferior es necesario argumentar sobre todos los circuitos al mismo tiempo.

Nótese que nos interesa el cálculo formal de polinomios, más que las funciones que definen los polinomios. Por ejemplo, consideremos el polinomioincógnita2+incógnita;{\displaystyle x^{2}+x;}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 los circuitos aritméticos y el de los circuitos booleanos . En la complejidad booleana, el interés principal radica en calcular una función, en lugar de su representación (en nuestro caso, mediante un polinomio). Esta es una de las razones por las que la complejidad booleana es más difícil que la aritmética. El estudio de los circuitos aritméticos también puede considerarse un paso intermedio hacia el estudio del caso booleano, [ 1 ] que aún no comprendemos del todo.

límites superiores

Como parte del estudio de la complejidad del cálculo de polinomios, se encontraron algunos circuitos ingeniosos (o algoritmos). Un ejemplo bien conocido es el algoritmo de Strassen para el producto de matrices . La forma directa de calcular el producto de dos matrices es...norte×norte{\displaystyle n\times n}Las matrices requieren un circuito de tamaño ordennorte3.{\displaystyle n^{3}.}Strassen demostró que, de hecho, podemos multiplicar dos matrices utilizando un circuito de tamaño aproximadamentenorte2.807.{\displaystyle n^{2.807}.}La idea básica de Strassen es una forma ingeniosa de multiplicar2×2{\displaystyle 2\times 2}matrices. Esta idea es el punto de partida de la mejor manera teórica de multiplicar dos matrices que toma tiempo aproximadamentenorte2.376.{\displaystyle n^{2.376}.}

Otra historia interesante se esconde tras el cálculo del determinante de unnorte×norte{\displaystyle n\times n}matriz. La forma ingenua de calcular el determinante requiere circuitos de tamaño aproximadamentenorte¡.{\displaystyle n!.}Sin embargo, sabemos que existen circuitos de tamaño polinomial ennorte{\displaystyle n}para calcular el determinante. Sin embargo, estos circuitos tienen una profundidad que es lineal ennorte.{\displaystyle n.}Berkowitz ideó una mejora: un circuito de tamaño polinomial ennorte,{\displaystyle n,}pero de profundidadO(registro2⁡(norte)).{\displaystyle O(\log ^{2}(n)).}[ 2 ]

También nos gustaría mencionar el mejor circuito conocido por la permanencia de unnorte×norte{\displaystyle n\times n}matriz. En cuanto al determinante, el circuito ingenuo para el permanente tiene un tamaño aproximadonorte¡.{\displaystyle n!.}Sin embargo, para el circuito permanente, el mejor circuito conocido tiene un tamaño aproximado2norte,{\displaystyle 2^{n},}que viene dada por la fórmula de Ryser: para unnorte×norte{\displaystyle n\times n}matrizincógnita=(incógnitai,j),{\displaystyle X=(x_{i,j}),}

permanente⁡(incógnita)=(−1)norte∑S⊆{1,…,norte}(−1)|S|∏i=1norte∑j∈Sincógnitai,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 demostrar cotas 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 grado22norte{\displaystyle 2^{2^{n}}}requieren un circuito de tamaño aproximadamente2norte.{\displaystyle 2^{n}.}Entonces, el objetivo principal es demostrar una cota inferior para polinomios de grado pequeño, digamos, polinomio ennorte.{\displaystyle n.}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 de la computación. 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 .

El estado del arte es unΩ(norteregistro⁡d){\displaystyle \Omega (n\log d)}límite inferior para el tamaño de un circuito de cálculo, por ejemplo, el polinomioincógnita1d+⋯+incógnitanorted{\displaystyle x_{1}^{d}+\cdots +x_{n}^{d}}dado por Strassen y por Baur y Strassen. Más precisamente, Strassen utilizó el teorema de Bézout para demostrar que cualquier circuito que calcule simultáneamente elnorte{\displaystyle n}polinomiosincógnita1d,…,incógnitanorted{\displaystyle x_{1}^{d},\ldots ,x_{n}^{d}}es de tamañoΩ(norteregistro⁡d),{\displaystyle \Omega (n\log d),}y más tarde Baur y Strassen demostraron lo siguiente: dado un circuito aritmético de tamaños{\displaystyle s}calcular un polinomioF,{\displaystyle f,}uno puede construir un nuevo circuito de tamaño como máximoO(s){\displaystyle O(s)}que calculaF{\displaystyle f}y todos losnorte{\displaystyle n}derivadas parciales deF.{\displaystyle f.}Dado que las derivadas parciales deincógnita1d+⋯+incógnitanorted{\displaystyle x_{1}^{d}+\cdots +x_{n}^{d}}sondincógnita1d−1,…,dincógnitanorted−1,{\displaystyle dx_{1}^{d-1},\ldots ,dx_{n}^{d-1},}El límite inferior de Strassen se aplica aincógnita1d+⋯+incógnitanorted{\displaystyle x_{1}^{d}+\cdots +x_{n}^{d}}también. [ 3 ] Este es un ejemplo donde una cota superior ayuda a demostrar cotas inferiores; la construcción de un circuito dado por Baur y Strassen implica una cota inferior para polinomios más generales.

La imposibilidad de demostrar cotas inferiores nos lleva a considerar modelos de computación más sencillos. 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 puerta lógica calcula un polinomio multilineal ). Estos modelos restringidos se han estudiado exhaustivamente 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 puede resolverse con la misma facilidad con la que se puede demostrar que existe una solución para dicho problema. En su obra fundamental, Valiant [ 4 ] propuso 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. F{\displaystyle f}de grado polinomial que tienen circuitos de tamaño polinomial sobre un campo fijoK.{\displaystyle K.}La clase VNP es el análogo de NP. VNP puede considerarse como la clase de polinomios.F{\displaystyle f}de grado polinomial tal que dado un monomio podemos determinar su coeficiente enF{\displaystyle f}de manera eficiente, con un circuito de tamaño polinomial.

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 completoF{\displaystyle f}para esta clase es un polinomio con dos propiedades: (1) es parte de la clase, y (2) cualquier otro polinomiogramo{\displaystyle g}en la clase es más fácil queF,{\displaystyle f,}en el sentido de que siF{\displaystyle f}tiene un circuito pequeño entonces tambiéngramo.{\displaystyle g.}Valiant demostró que el permanente es completo para la clase VNP. Por lo tanto, para demostrar que VP no es igual a VNP, es necesario demostrar que el permanente no tiene circuitos de tamaño polinomial. Este sigue siendo un problema abierto pendiente.

Reducción de profundidad

Un hito en nuestra comprensión del cálculo de polinomios es el trabajo de Valiant, Skyum, Berkowitz y Rackoff. [ 5 ] Demostraron que si un polinomioF{\displaystyle f}de grador{\displaystyle r}tiene un circuito de tamaños,{\displaystyle s,}entoncesF{\displaystyle f}también tiene un circuito de tamaño polinomial enr{\displaystyle r}ys{\displaystyle s}de profundidadO(registro⁡(r)registro⁡(s)).{\displaystyle O(\log(r)\log(s)).}Por ejemplo, cualquier polinomio de gradonorte{\displaystyle n}que tiene un circuito de tamaño polinomial, también tiene un circuito de tamaño polinomial de profundidad aproximadamenteregistro2⁡(norte).{\displaystyle \log ^{2}(n).}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 contexto booleano es falso.

Una consecuencia de este resultado es la simulación de circuitos mediante fórmulas relativamente pequeñas, fórmulas de tamaño cuasipolinomial: si un polinomioF{\displaystyle f}de grador{\displaystyle r}tiene un circuito de tamaños,{\displaystyle s,}entonces tiene una fórmula de tamañosO(registro⁡(r)).{\displaystyle s^{O(\log(r))}.}Esta simulación es más sencilla que la reducción de profundidad de Valiant et al. y fue mostrada anteriormente por Hyafil. [ 6 ]

Véase también

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

Lecturas adicionales

  • 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. Zbl 1087.68568 . 
  • von zur Gathen, Joachim (1988). "Teoría de la complejidad algebraica". Annual Review of Computer Science . 3 : 317–347 . doi : 10.1146/annurev.cs.03.060188.001533 .

Notas a pie de página

  1. ↑ LG Valiant. ¿Por qué es difícil la teoría de la complejidad booleana? Actas del simposio de la Sociedad Matemática de Londres sobre la complejidad de las funciones booleanas, págs. 84-94, 1992.
  2. ↑ SJ Berkowitz. Sobre el cálculo del determinante en tiempo paralelo reducido utilizando un número reducido de procesadores. Inf. Prod. Letters 18, pp. 147–150, 1984.
  3. ↑ Shpilka, Amir; Yehudayoff, Amir (2010). "Circuitos aritméticos: una revisión 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". Actas del undécimo simposio anual de la ACM sobre Teoría de la Computación - STOC '79 . ACM Press. págs. 249–261 . doi : 10.1145/800135.804419 . 
  5. ↑ Valiant, LG; Skyum, S.; Berkowitz, S.; Rackoff, C. (1983). "Cálculo paralelo rápido de polinomios con pocos procesadores" . SIAM Journal on Computing . 12 (4): 641– 644. doi : 10.1137/0212043 . ISSN 0097-5397 . 
  6. ↑ Hyafil, Laurent (1979). "Sobre la evaluación paralela de polinomios multivariados" . SIAM Journal on Computing . 8 (2): 120– 123. doi : 10.1137/0208010 . ISSN 0097-5397 .