Algebraisk kompleksitet

Algebraisk kompleksitet er en gren af beregningsmæssig kompleksitetsteori , der beskæftiger sig med polynomier. Det blev skabt hovedsageligt takket være F. Strassens arbejde [1] [2] [3] .

Algebraisk kompleksitet af et polynomium

Definition

Den algebraiske kompleksitet af et polynomium , som er betegnet med , er længden af det korteste ikke-forgrenende program, der beregner [4] . Et ikke-forgrenende program er en række funktioner defineret som følger: $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})

, …

hvor og er polynomier af første grad. Længden af et ikke-forgrenende program er antallet af termer i sekvensen . Et ikke-forgrenende program af længde beregner et polynomium , hvis . $EN$ $B$ $f_{1},...,f_{i},...$ $m$ $s$ $f_{m}=p$

Egenskaber

Der er et gradspolynomium i en variabel, hvis algebraiske kompleksitet er mindst . $n$ $\Omega ({\sqrt {n)))$

Uløste problemer

Ikke-trivielle nedre og øvre grænser for den algebraiske kompleksitet af partielle summer af udvidelsen af en funktion i en serie er ukendte . Der er en hypotese om, at for at beregne de første n led i denne serie, er det nødvendigt at udføre multiplikationer [5] . $e^{x}\sim 1+x+{\frac {x^{2}}{2}}+\ldots +{\frac {x^{n}}{n!)}}$ $\Omega (n)$
Ikke-trivielle nedre og øvre grænser for den algebraiske kompleksitet af partielle summer af udvidelsen af en funktion i en serie er ukendte . $\ln(1-x)\sim -x-{\frac {x^{2}}{2}}-\ldots -{\frac {x^{n}}{n!)}}$

Additiv matrix kompleksitet

Definition

Overvej operationen med at gange en kvadratisk matrix med konstante elementer: med en vektor . ${\begin{pmatrix}a_{11}&a_{12}&...&a_{1n}\\...&...&...&...\\a_{n1}&a_{ n2}&...&a_{nn}\end{pmatrix}}$ $x=(x_{1},...,x_{n})$

Den additive kompleksitet af en kvadratisk matrix er længden af den korteste sekvens af funktioner , der beregner produktet af en vektor og en tabelrække og er defineret som følger: , ..., , ... hvor , og er konstanter. $EN$ $f_{1},...,f_{i},...$ $x$ $j$ $EN$ $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}\in \venstre\{x_{1},...,x_{n},f_{1},...,f_{i-1}\right\ }$ $\alpha _{i},\beta _{i}$

Egenskaber

Den additive kompleksitet af en vilkårlig matrix er . For nogle typer matricer er det mindre. For eksempel for den hurtige Fourier-transformationsmatrix er den lig med . $O(n^{2})$ $O(n\log _{2}n)$

Klasse VP

Klassen VP er mængden af alle familier af polynomier , for hvilke . For eksempel hører problemet med at beregne determinanten af en matrix til VP-klassen. Beregningskompleksitetsklassen VP er en algebraisk analog til klassen P fra beregningskompleksitetsteorien [6] . $f_{{n}}$ $L(f_{n})\leqslant p(n)$

VNP-klasse

En VNP-klasse inkluderer en familie af polynomier , hvis den har en familie af polynomier fra VP-klassen, således at . Summeringen udføres over alle vektorer af nuller og længdeenheder og er lig med værdien af den -te koordinat af vektoren e. For eksempel hører problemet med at beregne permanenten af en matrix til VNP-klassen. VNP-beregningskompleksitetsklassen er en algebraisk analog til NP-klassen fra beregningsmæssig kompleksitetsteori. $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)$ ${\displaystyle e_{i))$ $jeg$

Noter

↑ Strassen, V. , Vermeidung von Divisionen, Crelles J. Reine Angew. Math 264, 1973, 184-202.
↑ Strassen V. Algebraic Complexity Theory // Håndbog i teoretisk datalogi. - Amsterdam: Elsevier, 1990. - PP. 633-672.
↑ Razborov, 2016 , s. 3.
↑ Razborov, 2016 , s. otte.
↑ Razborov, 2016 , s. 9.
↑ Razborov, 2016 , s. 22.

Litteratur

Razborov A. A. Algebraisk kompleksitet. — M .: MTsNMO , 2016. — 32 s. - ISBN 978-5-4439-1032-1 .