Algebrai komplexitás

Az algebrai komplexitás a számítási komplexitáselmélet polinomokkal foglalkozó ága . Elsősorban F. Strassen [1] [2] [3] munkájának köszönhetően jött létre .

Polinom algebrai összetettsége

Definíció

Egy polinom algebrai komplexitása , amelyet -vel jelölünk , annak a legrövidebb, nem elágazó programnak a hossza, amely kiszámítja [4] . A nem elágazó program a következőképpen meghatározott függvénysorozat: $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})

, …

ahol és az elsőfokú polinomok. Egy nem elágazó program hossza a szekvencia kifejezéseinek száma . Egy nem elágazó hosszúságú program egy polinomot számít ki, ha . $A$ $B$ $f_{1},...,f_{i},...$ $m$ $p$ $f_{m}=p$

Tulajdonságok

Egy változóban van egy fokszámú polinom, amelynek algebrai összetettsége legalább . $n$ $\Omega ({\sqrt {n)))$

Megoldatlan problémák

Nem triviális alsó és felső korlátok egy sorozatban lévő függvény kiterjesztésének parciális összegeinek algebrai komplexitására nem ismertek . Van egy hipotézis, hogy ennek a sorozatnak az első n tagjának kiszámításához szorzást kell végezni [5] . $e^{x}\sim 1+x+{\frac {x^{2}}{2}}+\ldots +{\frac {x^{n}}{n!)}}$ $\Omega (n)$
Nem triviális alsó és felső korlátok egy sorozatban lévő függvény kiterjesztésének parciális összegeinek algebrai komplexitására nem ismertek . $\ln(1-x)\sim -x-{\frac {x^{2}}{2}}-\ldots -{\frac {x^{n}}{n!)}}$

Additív mátrix komplexitás

Definíció

Tekintsük egy négyzetes mátrix állandó elemekkel való szorzásának műveletét: egy vektorral . ${\begin{pmatrix}a_{11}&a_{12}&...&a_{1n}\\...&...&...&...\\a_{n1}&a_{ n2}&...&a_{nn}\end{pmatrix}}$ $x=(x_{1},...,x_{n})$

A négyzetmátrix additív összetettsége a vektor és a táblázat sorának szorzatát kiszámító függvények legrövidebb sorozatának hossza, és a következőképpen definiálható: , ..., , ... ahol , és állandók. $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}$

Tulajdonságok

Egy tetszőleges mátrix additív összetettsége a . Bizonyos típusú mátrixok esetében ez kevesebb. Például a gyors Fourier-transzformációs mátrix esetén egyenlő: . $O(n^{2})$ $O(n\log _{2}n)$

osztály VP

A VP osztály az összes olyan polinomcsalád halmaza, amelyre . Például egy mátrix determinánsának kiszámítása a VP osztályba tartozik. A VP számítási komplexitási osztály a számítási komplexitáselmélet P osztályának algebrai analógja [6] . $f_{{n}}$ $L(f_{n})\leqslant p(n)$

VNP osztály

Egy VNP osztály polinomcsaládot tartalmaz, ha van olyan polinomcsaládja a VP osztályból, hogy . Az összegzést minden nulla és hosszmértékegység vektorán végrehajtjuk , és megegyezik az e vektor -edik koordinátájának értékével. Például egy mátrix állandójának kiszámítása a VNP osztályba tartozik. A VNP számítási komplexitási osztály a számítási komplexitáselmélet NP osztályának algebrai analógja . $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))$ $én$

Jegyzetek

↑ Strassen, V. , Vermeidung von Divisionen, Crelles J. Reine Angew. Math 264, 1973, 184-202.
↑ Strassen V. Algebrai komplexitáselmélet // Az elméleti számítástechnika kézikönyve. - Amszterdam: Elsevier, 1990. - PP. 633-672.
↑ Elemzés, 2016 , p. 3.
↑ Elemzés, 2016 , p. nyolc.
↑ Elemzés, 2016 , p. 9.
↑ Elemzés, 2016 , p. 22.

Irodalom

Razborov A. A. Algebrai komplexitás. — M .: MTsNMO , 2016. — 32 p. - ISBN 978-5-4439-1032-1 .