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

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

Определение

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

${\displaystyle f_{1}=A_{1}(x_{1},...,x_{k})B_{1}(x_{1},...,x_{k})}$ ,

…

${\displaystyle f_{i}=A_{i}(x_{1},...,x_{k},f_{1},...,f_{i-1})B_{i}(x_{1},...,x_{k},f_{1},...,f_{i-1})}$ ,

…

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

Свойства

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

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

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

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

Определение

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

Аддитивной сложностью квадратной матрицы ${\displaystyle A}$ называется длина самой короткой последовательности функций ${\displaystyle f_{1},...,f_{i},...}$ , вычисляющих произведение вектора ${\displaystyle x}$ на ${\displaystyle j}$ строку таблицы ${\displaystyle A}$ и определённых следующим образом: ${\displaystyle f_{1}=\alpha _{1}u_{1}+\beta _{1}v_{1}}$ , ..., ${\displaystyle f_{i}=\alpha _{i}u_{i}+\beta _{i}v_{i}}$ , ... где ${\displaystyle u_{i},v_{i}\in \left\{x_{1},...,x_{n},f_{1},...,f_{i-1}\right\}}$ , а ${\displaystyle \alpha _{i},\beta _{i}}$ являются постоянными.

Свойства

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

Класс VP

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

Класс VNP

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

Примечания

Литература

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