Complexitatea algebrică

Complexitatea algebrică este o ramură a teoriei complexității computaționale care se ocupă de polinoame. A fost creată în principal datorită lucrării lui F. Strassen [1] [2] [3] .

Complexitatea algebrică a unui polinom

Definiție

Complexitatea algebrică a unui polinom , care se notează cu , este lungimea celui mai scurt program neramificat care calculează [4] . Un program non-ramificat este o secvență de funcții definită după cum urmează: $f$ $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})

, …

unde și sunt polinoame de gradul I. Lungimea unui program neramificat este numărul de termeni din secvența . Un program neramificat de lungime calculează un polinom dacă . $A$ $B$ $f_{1},...,f_{i},...$ $m$ $p$ $f_{m}=p$

Proprietăți

Există un polinom de grad într-o variabilă a cărei complexitate algebrică este de cel puțin . $n$ $\Omega ({\sqrt {n))}$

Probleme nerezolvate

Limitele inferioare și superioare non-triviale pentru complexitatea algebrică a sumelor parțiale ale expansiunii unei funcții într-o serie sunt necunoscute . Există o ipoteză că pentru a calcula primii n termeni ai acestei serii este necesară efectuarea înmulțirilor [5] . $e^{x}\sim 1+x+{\frac {x^{2}}{2}}+\ldots +{\frac {x^{n}}{n!)}}$ $\Omega (n)$
Limitele inferioare și superioare non-triviale pentru complexitatea algebrică a sumelor parțiale ale expansiunii unei funcții într-o serie sunt necunoscute . $\ln(1-x)\sim -x-{\frac {x^{2}}{2}}-\ldots -{\frac {x^{n}}{n!)}}$

Complexitatea matricei aditive

Definiție

Se consideră operația de înmulțire a unei matrice pătrate cu elemente constante: printr-un vector . ${\begin{pmatrix}a_{11}&a_{12}&...&a_{1n}\\...&...&...&...\\a_{n1}&a_{ n2}&...&a_{nn}\end{pmatrix}}$ $x=(x_{1},...,x_{n})$

Complexitatea aditivă a unei matrice pătrate este lungimea celei mai scurte secvențe de funcții care calculează produsul unui vector și un rând de tabel și sunt definite după cum urmează: , ..., , ... unde și sunt constante. $A$ $f_{1},...,f_{i},...$ $X$ $j$ $A$ $f_{1}=\alpha _{1}u_{1}+\beta _{1}v_{1)$ $f_{i}=\alpha _{i}u_{i}+\beta _{i}v_{i)$ $u_{i},v_{i}\in \left\{x_{1},...,x_{n},f_{1},...,f_{i-1}\right\ }$ $\alpha _{i},\beta _{i}$

Proprietăți

Complexitatea aditivă a unei matrice arbitrare este . Pentru unele tipuri de matrice, este mai puțin. De exemplu, pentru matricea transformată Fourier rapidă , aceasta este egală cu . $O(n^{2})$ $O(n\log _{2}n)$

Clasa VP

Clasa VP este mulțimea tuturor familiilor de polinoame pentru care . De exemplu, problema calculării determinantului unei matrice aparține clasei VP. Clasa de complexitate computațională VP este un analog algebric al clasei P din teoria complexității computaționale [6] . $f_{{n}}$ $L(f_{n})\leqslant p(n)$

Clasa VNP

O clasă VNP include o familie de polinoame dacă are o familie de polinoame din clasa VP astfel încât . Însumarea se efectuează pe toți vectorii de zerouri și unități de lungime și este egală cu valoarea coordonatei --a a vectorului e. De exemplu, problema calculării permanentei unei matrice aparține clasei VNP. Clasa de complexitate computațională VNP este un analog algebric al clasei NP din teoria complexității computaționale. $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)})$ $e$ $k(n)$ $e_{i}$ $i$

Note

↑ Strassen, V. , Vermeidung von Divisionen, Crelles J. Reine Angew. Math 264, 1973, 184-202.
↑ Strassen V. Teoria complexității algebrice // Manual de informatică teoretică. - Amsterdam: Elsevier, 1990. - PP. 633-672.
↑ Razborov, 2016 , p. 3.
↑ Razborov, 2016 , p. opt.
↑ Razborov, 2016 , p. 9.
↑ Razborov, 2016 , p. 22.

Literatură

Razborov A. A. Complexitatea algebrică. — M .: MTsNMO , 2016. — 32 p. - ISBN 978-5-4439-1032-1 .