Complejidad algebraica

La complejidad algebraica es una rama de la teoría de la complejidad computacional que trata con polinomios. Fue creado principalmente gracias al trabajo de F. Strassen [1] [2] [3] .

Complejidad algebraica de un polinomio

Definición

La complejidad algebraica de un polinomio , que se denota por , es la longitud del programa no ramificado más corto que calcula [4] . Un programa sin ramificación es una secuencia de funciones definida de la siguiente manera: $F$ ${\ estilo de visualización L (f)}$ $F$ $f_{1},...,f_{i},...$

f_{1}=A_{1}(x_{1},...,x_{k})B_{1}(x_{1},...,x_{k})

, …

f_{i}=A_{i}(x_{1},...,x_{k},f_{1},...,f_{i-1})B_{i}(x_{ 1},...,x_{k},f_{1},...,f_{i-1})

, …

donde y son polinomios de primer grado. La longitud de un programa sin ramificación es el número de términos en la secuencia . Un programa de longitud que no se ramifica calcula un polinomio si . $A$ $B$ $f_{1},...,f_{i},...$ $metro$ $pags$ ${\ estilo de visualización f_ {m} = p}$

Propiedades

Existe un polinomio de grado en una variable cuya complejidad algebraica es al menos . $norte$ ${\displaystyle\Omega ({\sqrt {n)))}$

Cuestiones no resueltas

Se desconocen los límites superior e inferior no triviales para la complejidad algebraica de las sumas parciales de la expansión de una función en una serie . Existe la hipótesis de que para calcular los primeros n términos de esta serie, se requiere realizar multiplicaciones [5] . $e^{x}\sim 1+x+{\frac {x^{2}}{2}}+\ldots +{\frac {x^{n}}{n!)}}$ ${\ estilo de visualización \ Omega (n)}$
Se desconocen los límites superior e inferior no triviales para la complejidad algebraica de las sumas parciales de la expansión de una función en una serie . $\ln(1-x)\sim -x-{\frac {x^{2}}{2}}-\ldots -{\frac {x^{n}}{n!)}}$

Complejidad de la matriz aditiva

Definición

Considere la operación de multiplicar una matriz cuadrada con elementos constantes: por un vector . ${\begin{pmatrix}a_{11}&a_{12}&...&a_{1n}\\...&...&...&...\\a_{n1}&a_{ n2}&...&a_{nn}\end{matrix}}$ ${\ estilo de visualización x = (x_{1},...,x_{n})}$

La complejidad aditiva de una matriz cuadrada es la longitud de la secuencia más corta de funciones que calculan el producto de un vector y una fila de la tabla y se definen de la siguiente manera: , ..., , ... donde , y son constantes. $A$ $f_{1},...,f_{i},...$ $X$ $j$ $A$ ${\displaystyle f_{1}=\alpha _{1}u_{1}+\beta _{1}v_{1))$ ${\displaystyle f_{i}=\alpha _{i}u_{i}+\beta _{i}v_{i))$ $u_{i},v_{i}\en \izquierda\{x_{1},...,x_{n},f_{1},...,f_{i-1}\derecha\ }$ ${\ estilo de visualización \ alfa _ {i}, \ beta _ {i}}$

Propiedades

La complejidad aditiva de una matriz arbitraria es . Para algunos tipos de matrices, es menor. Por ejemplo, para la matriz de transformada rápida de Fourier , es igual a . ${\ estilo de visualización O (n ^ {2})}$ ${\ estilo de visualización O (n \ log _ {2} n)}$

VP de clase

La clase VP es el conjunto de todas las familias de polinomios para los que . Por ejemplo, el problema de calcular el determinante de una matriz pertenece a la clase VP. La clase de complejidad computacional VP es un análogo algebraico de la clase P de la teoría de la complejidad computacional [6] . $f_{{n}}$ $L(f_{n})\leqslant p(n)$

clase VNP

Una clase VNP incluye una familia de polinomios si tiene una familia de polinomios de la clase VP tal que . La suma se realiza sobre todos los vectores de ceros y unidades de longitud , y es igual al valor de la coordenada -ésima del vector e. Por ejemplo, el problema de calcular el permanente de una matriz pertenece a la clase VNP. La clase de complejidad computacional VNP es un análogo algebraico de la clase NP de la teoría de la complejidad computacional. $f_{n}(x_{1},...,x_{m(n)})$ $\left\{g_{n}(x_{1},...,x_{m(n)},y_{1},...,y_{k(n)})\right\}$ $f_{n}(x_{1},...,x_{m(n)})=\sum_{e\in \left\{0,1\right\}^{k(n) }}^{}g_{n}(x_{1},...,x_{m(n)},e_{1},...,e_{k(n)})$ $mi$ ${\ estilo de visualización k (n)}$ ${\ Displaystyle e_ {yo}}$ $i$

Notas

↑ Strassen, V. , Vermeidung von Divisionen, Crelles J. Reine Angew. Matemáticas 264, 1973, 184-202.
↑ Strassen V. Teoría de la complejidad algebraica // Manual de informática teórica. - Ámsterdam: Elsevier, 1990. - PP. 633-672.
↑ Razborov, 2016 , pág. 3.
↑ Razborov, 2016 , pág. ocho.
↑ Razborov, 2016 , pág. 9.
↑ Razborov, 2016 , pág. 22

Literatura

Razborov A. A. Complejidad algebraica. — M .: MTsNMO , 2016. — 32 p. - ISBN 978-5-4439-1032-1 .