Алгебраическая сложность

Алгебраическая сложность — раздел теории сложности вычислений, имеющий дело с полиномами. Был создан в основном благодаря работам Ф. Штрассена.

Алгебраическая сложность полиномаПравить

ОпределениеПравить

Алгебраической сложностью полинома $f$$f$ , которую обозначают через $L(f)$$L(f)$ , называется длина кратчайшей неветвящейся программы, вычисляющей $f$$f$ . Неветвящейся программой называется последовательность функций $f_1,...,f_i,...$$f_{1},...,f_{i},...$ , определённая следующим образом:

$f_1=A_1(x_1,...,x_k)B_1(x_1,...,x_k)$$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})$$f_{i}=A_{i}(x_{1},...,x_{k},f_{1},...,f_{i-1})B_{i}(x_{1},...,x_{k},f_{1},...,f_{i-1})$ ,

…

где $A$$A$  и $B$$B$  — полиномы первой степени. Длиной неветвящейся программы называется число членов в последовательности $f_1,...,f_i,...$$f_{1},...,f_{i},...$ . Неветвящаяся программа длиной $m$$m$  вычисляет полином $p$$p$ , если $f_m=p$$f_{m}=p$ .

СвойстваПравить

• Существует полином степени $n$$n$  от одной переменной, алгебраическая сложность которого не меньше $\mathrm{\Omega <!--\; \Omega \; -->}(\sqrt{n})$$\Omega ({\sqrt {n}})$ .

Нерешённые проблемыПравить

• Неизвестны нетривиальные нижние и верхние оценки алгебраической сложности частичных сумм разложения функции в ряд $e^x\sim <!--\; \sim \; -->1+x+\frac{x^2}{2}+\dots <!--\; \dots \; -->+\frac{x^n}{n!}$$e^{x}\sim 1+x+{\frac {x^{2}}{2}}+\ldots +{\frac {x^{n}}{n!}}$ . Существует гипотеза, что для вычисления первых n слагаемых этого ряда требуется выполнить $\mathrm{\Omega <!--\; \Omega \; -->}(n)$$\Omega (n)$  умножений.
• Неизвестны нетривиальные нижние и верхние оценки алгебраической сложности частичных сумм разложения функции в ряд $\ln <!--\; \; -->(1-<!--\; -\; -->x)\sim <!--\; \sim \; -->-<!--\; -\; -->x-<!--\; -\; -->\frac{x^2}{2}-<!--\; -\; -->\dots <!--\; \dots \; -->-<!--\; -\; -->\frac{x^n}{n!}$$\ln(1-x)\sim -x-{\frac {x^{2}}{2}}-\ldots -{\frac {x^{n}}{n!}}$ .

Аддитивная сложность матрицыПравить

ОпределениеПравить

Рассмотрим операцию умножения квадратной матрицы с постоянными элементами: ${\begin{pmatrix}a_{11}&a_{12}&...&a_{1n}\\...&...&...&...\\a_{n1}&a_{n2}&...&a_{nn}\end{pmatrix}}$  на вектор $x=(x_1,...,x_n)$$x=(x_{1},...,x_{n})$ .

Аддитивной сложностью квадратной матрицы $A$$A$  называется длина самой короткой последовательности функций $f_1,...,f_i,...$$f_{1},...,f_{i},...$ , вычисляющих произведение вектора $x$$x$  на $j$$j$  строку таблицы $A$$A$  и определённых следующим образом: $f_1={\mathrm{\alpha <!--\; \alpha \; -->}}_1{u}_1+{\mathrm{\beta <!--\; \beta \; -->}}_1{v}_1$$f_{1}=\alpha _{1}u_{1}+\beta _{1}v_{1}$ , ...,$f_i={\mathrm{\alpha <!--\; \alpha \; -->}}_i{u}_i+{\mathrm{\beta <!--\; \beta \; -->}}_i{v}_i$$f_{i}=\alpha _{i}u_{i}+\beta _{i}v_{i}$ , ... где $u_i,v_i\in <!--\; \in \; -->\left\{x_1,...,x_n,f_1,...,f_{i-<!--\; -\; -->1}\right\}$$u_{i},v_{i}\in \left\{x_{1},...,x_{n},f_{1},...,f_{i-1}\right\}$ , а ${\mathrm{\alpha <!--\; \alpha \; -->}}_i,{\mathrm{\beta <!--\; \beta \; -->}}_i$$\alpha _{i},\beta _{i}$  являются постоянными.

СвойстваПравить

• Аддитивная сложность произвольной матрицы равна $O(n^2)$$O(n^{2})$ . У некоторых видов матриц она меньше. Например, у матрицы быстрого преобразования Фурье, она равна $O(n{\log }_2<!--\; \; -->n)$$O(n\log _{2}n)$ .

Класс VPПравить

Классом VP называется множество всех семейств полиномов $f_n$$f_{{n}}$ , для которых $L(f_n)⩽<!--\; ⩽\; -->p(n)$$L(f_{n})\leqslant p(n)$ . Например, задача вычисления детерминанта матрицы принадлежит классу VP. Класс сложности вычислений VP является алгебраическим аналогом класса P из теории сложности вычислений.

Класс VNPПравить

Класс VNP включает в себя семейство полиномов $f_n(x_1,...,x_{m(n)})$$f_{n}(x_{1},...,x_{m(n)})$ , если для него найдется семейство полиномов $\left\{g_n(x_1,...,x_{m(n)},y_1,...,y_{k(n)})\right\}$$\left\{g_{n}(x_{1},...,x_{m(n)},y_{1},...,y_{k(n)})\right\}$  из класса VP такое, что выполнено равенство $f_n(x_1,...,x_{m(n)})=\underset{e\in <!--\; \in \; -->{\left\{0,1\right\}}^{k(n)}}{\overset{}{\sum <!--\; \sum \; -->}}{g}_n(x_1,...,x_{m(n)},e_1,...,e_{k(n)})$$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$$e$  из нулей и единиц длины $k(n)$$k(n)$ , а $e_i$$e_{i}$  равно значению $i$$i$ -й координаты вектора e. Например, задача вычисления перманента матрицы принадлежит классу VNP. Класс сложности вычислений VNP является алгебраическим аналогом класса NP из теории сложности вычислений.

ЛитератураПравить

• Разборов А. А. Алгебраическая сложность. — М.: МЦНМО, 2016. — 32 с. — ISBN 978-5-4439-1032-1.