Algebrallinen monimutkaisuus

Algebrallinen monimutkaisuus on laskennallisen monimutkaisuusteorian haara , joka käsittelee polynomeja. Se syntyi pääasiassa F. Strassenin [1] [2] [3] ansiosta .

Polynomin algebrallinen monimutkaisuus

Määritelmä

Polynomin algebrallinen monimutkaisuus , jota merkitään , on lyhimmän ei-haarautuneen ohjelman pituus, joka laskee [4] . Haaroittumaton ohjelma on funktiosarja, joka määritellään seuraavasti: $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})

, …

missä ja ovat ensimmäisen asteen polynomeja. Haaroittumattoman ohjelman pituus on sekvenssin termien määrä . Haarautumaton pituusohjelma laskee polynomin , jos . $A$ $B$ $f_{1},...,f_{i},...$ $m$ $s$ $f_{m}=p$

Ominaisuudet

Yhdessä muuttujassa on astepolynomi, jonka algebrallinen monimutkaisuus on vähintään . $n$ $\Omega ({\sqrt {n)))$

Ratkaisemattomat ongelmat

Ei-triviaaliset ala- ja ylärajat sarjan funktion laajennuksen osittaisten summien algebralliselle kompleksisuudelle ovat tuntemattomia . On olemassa hypoteesi, että tämän sarjan ensimmäisen n ehdon laskeminen edellyttää kertolaskujen suorittamista [5] . $e^{x}\sim 1+x+{\frac {x^{2}}{2}}+\ldots +{\frac {x^{n}}{n!)}}$ $\Omega (n)$
Ei-triviaaliset ala- ja ylärajat sarjan funktion laajennuksen osittaisten summien algebralliselle kompleksisuudelle ovat tuntemattomia . $\ln(1-x)\sim -x-{\frac {x^{2}}{2}}-\ldots -{\frac {x^{n}}{n!)}}$

Additiivisen matriisin monimutkaisuus

Määritelmä

Tarkastellaan operaatiota, jossa neliömatriisi kerrotaan vakioelementeillä: vektorilla . ${\begin{pmatrix}a_{11}&a_{12}&...&a_{1n}\\...&...&...&...\\a_{n1}&a_{ n2}&...&a_{nn}\end{pmatrix}}$ $x=(x_{1},...,x_{n})$

Neliömatriisin additiivinen kompleksisuus on lyhimmän funktiosarjan pituus, joka laskee vektorin ja taulukon rivin tulon ja määritellään seuraavasti: , ..., , ... missä , ja ovat vakioita. $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}$

Ominaisuudet

Mielivaltaisen matriisin additiivinen monimutkaisuus on . Joidenkin matriisityyppien kohdalla se on pienempi. Esimerkiksi nopealle Fourier-muunnosmatriisille se on yhtä suuri kuin . $O(n^{2})$ $O(n\log _{2}n)$

Luokan VP

Luokka VP on joukko kaikista polynomiperheistä , joille . Esimerkiksi matriisin determinantin laskentaongelma kuuluu VP-luokkaan. Laskennallinen monimutkaisuusluokka VP on luokan P algebrallinen analogi laskennallisen kompleksisuusteorian [ 6] . $f_{{n}}$ $L(f_{n})\leqslant p(n)$

VNP-luokka

VNP-luokka sisältää polynomiperheen, jos sillä on polynomiperhe VP-luokasta siten, että . Summaus suoritetaan kaikkien nollien ja pituusyksiköiden vektoreille , ja se on yhtä suuri kuin vektorin e koordinaatin arvo. Esimerkiksi matriisin pysyvän laskemisen ongelma kuuluu VNP-luokkaan. VNP:n laskennallinen kompleksisuusluokka on NP-luokan algebrallinen analogi laskennallisen monimutkaisuusteorian perusteella. $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$

Muistiinpanot

↑ Strassen, V. , Vermeidung von Divisionen, Crelles J. Reine Angew. Math 264, 1973, 184-202.
↑ Strassen V. Algebrallinen kompleksiteoria // Tietojenkäsittelyteorian käsikirja. - Amsterdam: Elsevier, 1990. - PP. 633-672.
↑ Razborov, 2016 , s. 3.
↑ Razborov, 2016 , s. kahdeksan.
↑ Razborov, 2016 , s. 9.
↑ Razborov, 2016 , s. 22.

Kirjallisuus

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