Algebraická složitost

Algebraická složitost je odvětví teorie výpočetní složitosti , které se zabývá polynomy. Vznikla především díky dílu F. Strassena [1] [2] [3] .

Algebraická složitost polynomu

Definice

Algebraická složitost polynomu , který se značí , je délka nejkratšího nevětveného programu, který počítá [4] . Nevětvený program je posloupnost funkcí definovaná takto: $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})

, …

kde a jsou polynomy prvního stupně. Délka nevětveného programu je počet termínů v sekvenci . Nevětvený program délky počítá polynom if . $A$ $B$ $f_{1},...,f_{i},...$ $m$ $p$ $f_{m}=p$

Vlastnosti

V jedné proměnné je polynom stupně , jehož algebraická složitost je nejméně . $n$ $\Omega ({\sqrt {n)))$

Nevyřešené problémy

Netriviální dolní a horní hranice pro algebraickou složitost částečných součtů rozvoje funkce v řadě jsou neznámé . Existuje hypotéza, že pro výpočet prvních n členů této řady je nutné provést násobení [5] . $e^{x}\sim 1+x+{\frac {x^{2}}{2}}+\ldots +{\frac {x^{n}}{n!)}}$ $\Omega (n)$
Netriviální dolní a horní hranice pro algebraickou složitost částečných součtů rozvoje funkce v řadě jsou neznámé . $\ln(1-x)\sim -x-{\frac {x^{2}}{2}}-\ldots -{\frac {x^{n}}{n!)}}$

Složitost aditivní matice

Definice

Zvažte operaci násobení čtvercové matice s konstantními prvky: vektorem . ${\begin{pmatrix}a_{11}&a_{12}&...&a_{1n}\\...&...&...&...\\a_{n1}&a_{ n2}&...&a_{nn}\end{pmatrix}}$ $x=(x_{1},...,x_{n})$

Aditivní složitost čtvercové matice je délka nejkratší sekvence funkcí , které počítají součin vektoru a řádku tabulky a jsou definovány takto: , ..., , ... kde , a jsou konstanty. $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}$

Vlastnosti

Aditivní složitost libovolné matice je . U některých typů matic je to méně. Například pro matici rychlé Fourierovy transformace se rovná . $O(n^{2})$ $O(n\log _{2}n)$

Třída VP

Třída VP je množina všech rodin polynomů, pro které . Například problém výpočtu determinantu matice patří do třídy VP. Třída výpočetní složitosti VP je algebraickou obdobou třídy P z teorie výpočetní složitosti [6] . $f_{{n}}$ $L(f_{n})\leqslant p(n)$

Třída VNP

Třída VNP zahrnuje rodinu polynomů , pokud má rodinu polynomů z třídy VP takovou, že . Suma se provádí přes všechny vektory nul a jednotek délky a rovná se hodnotě -té souřadnice vektoru e. Například problém výpočtu permanentu matice patří do třídy VNP. Třída výpočetní složitosti VNP je algebraickou analogií třídy NP z teorie výpočetní složitosti. $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)})=\součet _{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$

Poznámky

↑ Strassen, V. , Vermeidung von Divisionen, Crelles J. Reine Angew. Matematika 264, 1973, 184-202.
↑ Strassen V. Algebraická teorie složitosti // Příručka teoretické informatiky. - Amsterdam: Elsevier, 1990. - PP. 633-672.
↑ Razborov, 2016 , str. 3.
↑ Razborov, 2016 , str. osm.
↑ Razborov, 2016 , str. 9.
↑ Razborov, 2016 , str. 22.

Literatura

Razborov A. A. Algebraická složitost. — M .: MTsNMO , 2016. — 32 s. - ISBN 978-5-4439-1032-1 .