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

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

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

Определение

Алгебраической сложностью полинома $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$ от одной переменной, алгебраическая сложность которого не меньше $\Omega ({\sqrt {n}})$.

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

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

Аддитивной сложностью квадратной матрицы $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}$ являются постоянными.

Свойства

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

Класс VP

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

Класс VNP

Класс VNP включает в себя семейство полиномов $f_{n}(x_{1},...,x_{m(n)})$, если для него найдется семейство полиномов $\left\{g_{n}(x_{1},...,x_{m(n)},y_{1},...,y_{k(n)})\right\}$ из класса VP такое, что выполнено равенство $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$-й координаты вектора e. Например, задача вычисления перманента матрицы принадлежит классу VNP. Класс сложности вычислений VNP является алгебраическим аналогом класса NP из теории сложности вычислений.

Литература

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