Algebraisk komplexitet

Algebraisk komplexitet är en gren av beräkningskomplexitetsteorin som behandlar polynom. Den skapades främst tack vare F. Strassens arbete [1] [2] [3] .

Algebraisk komplexitet för ett polynom

Definition

Den algebraiska komplexiteten för ett polynom , som betecknas med , är längden på det kortaste icke-förgrenade programmet som beräknar [4] . Ett icke-grenprogram är en sekvens av funktioner som definieras enligt följande: $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})

, …

där och är polynom av första graden. Längden på ett icke-grenprogram är antalet termer i sekvensen . Ett icke-förgrenande program med längd beräknar ett polynom om . $A$ $B$ $f_{1},...,f_{i},...$ $m$ $sid$ $f_{m}=p$

Egenskaper

Det finns ett gradpolynom i en variabel vars algebraiska komplexitet är minst . $n$ $\Omega ({\sqrt {n)))$

Olösta problem

Icke-triviala nedre och övre gränser för den algebraiska komplexiteten hos delsummor av expansionen av en funktion i en serie är okända . Det finns en hypotes att för att beräkna de första n termerna i denna serie krävs det att man utför multiplikationer [5] . $e^{x}\sim 1+x+{\frac {x^{2}}{2}}+\ldots +{\frac {x^{n}}{n!)}}$ $\Omega (n)$
Icke-triviala nedre och övre gränser för den algebraiska komplexiteten hos delsummor av expansionen av en funktion i en serie är okända . $\ln(1-x)\sim -x-{\frac {x^{2}}{2}}-\ldots -{\frac {x^{n}}{n!)}}$

Additiv matriskomplexitet

Definition

Överväg operationen att multiplicera en kvadratisk matris med konstanta element: 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 additiva komplexiteten hos en kvadratisk matris är längden på den kortaste sekvensen av funktioner som beräknar produkten av en vektor och en tabellrad och definieras enligt följande: , ..., , ... där , och är konstanter. $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}\in \left\{x_{1},...,x_{n},f_{1},...,f_{i-1}\right\ }$ $\alpha _{i},\beta _{i}$

Egenskaper

Den additiva komplexiteten hos en godtycklig matris är . För vissa typer av matriser är det mindre. Till exempel, för den snabba Fourier-transformmatrisen är den lika med . $O(n^{2})$ $O(n\log _{2}n)$

Klass VP

Klassen VP är mängden av alla familjer av polynom för vilka . Till exempel hör problemet med att beräkna determinanten för en matris till VP-klassen. Beräkningskomplexitetsklassen VP är en algebraisk analog till klassen P från beräkningskomplexitetsteorin [6] . $f_{{n}}$ $L(f_{n})\leqslant p(n)$

VNP-klass

En VNP-klass inkluderar en familj av polynom om den har en familj av polynom från VP-klassen så att . Summeringen utförs över alla vektorer av nollor och längdenheter och är lika med värdet av den -:e koordinaten för vektorn e. Till exempel hör problemet med att beräkna en matris permanent till VNP-klassen. VNP-beräkningskomplexitetsklassen är en algebraisk analog till NP-klassen från beräkningskomplexitetsteorin. $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)})=\summa _{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))$ $i$

Anteckningar

↑ Strassen, V. , Vermeidung von Divisionen, Crelles J. Reine Angew. Math 264, 1973, 184-202.
↑ Strassen V. Algebraisk komplexitetsteori // Handbook of theoretical data science. - Amsterdam: Elsevier, 1990. - PP. 633-672.
↑ Razborov, 2016 , sid. 3.
↑ Razborov, 2016 , sid. åtta.
↑ Razborov, 2016 , sid. 9.
↑ Razborov, 2016 , sid. 22.

Litteratur

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