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

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

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

Определение

Алгебраической сложностью полинома $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})$,

…

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

Свойства

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

Нерешённые проблемы

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

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

Определение

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

Аддитивной сложностью квадратной матрицы $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 \{x_1,...,x_n,f_1,...,f_{i-1}\}$, а ${\alpha }_i,{\beta }_i$ являются постоянными.

Свойства

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

Класс VP

Классом VP называется множество всех семейств полиномов $f_n$, для которых $L(f_n)⩽p(n)$. Например, задача вычисления детерминанта матрицы принадлежит классу VP. Класс сложности вычислений VP является алгебраическим аналогом класса P из теории сложности вычислений.

Класс VNP

Класс VNP включает в себя семейство полиномов $f_n(x_1,...,x_{m(n)})$, если для него найдется семейство полиномов $\{g_n(x_1,...,x_{m(n)},y_1,...,y_{k(n)})\}$ из класса VP такое, что выполнено равенство $f_n(x_1,...,x_{m(n)})=\sum _{e\in {\{0,1\}}^{k(n)}}^{}{g}_n(x_1,...,x_{m(n)},e_1,...,e_{k(n)})$. Суммирование ведется по всем векторам $e$ из нулей и единиц длины $k(n)$, а $e_i$ равно значению $i$-й координаты вектора e. Например, задача вычисления перманента матрицы принадлежит классу VNP. Класс сложности вычислений VNP является алгебраическим аналогом класса NP из теории сложности вычислений.

Литература

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