Меню Главная Случайная статья Настройки Алгебраическая сложность Материал из https://ru.wikipedia.org Алгебраическая сложность — раздел теории сложности вычислений, имеющий дело с полиномами. Был создан в основном благодаря работам Ф. Штрассена[1][2][3]. Содержание 1 Алгебраическая сложность полинома 1.1 Определение 1.2 Свойства 1.3 Нерешённые проблемы 2 Аддитивная сложность матрицы 2.1 Определение 2.2 Свойства 3 Класс VP 4 Класс VNP 5 Примечания 6 Литература Алгебраическая сложность полинома Определение Алгебраической сложностью полинома ${\displaystyle f}$, которую обозначают через ${\displaystyle L(f)}$, называется длина кратчайшей неветвящейся программы, вычисляющей ${\displaystyle f}$[4]. Неветвящейся программой называется последовательность функций ${\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)}$ умножений[5]. Неизвестны нетривиальные нижние и верхние оценки алгебраической сложности частичных сумм разложения функции в ряд ${\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 из теории сложности вычислений[6]. Класс 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 из теории сложности вычислений. Примечания Strassen, V., Vermeidung von Divisionen, Crelles J.Reine Angew. Math 264, 1973, 184-202. Strassen V. Algebraic Complexity Theory // Handbook of theoretical computer science. — Amsterdam: Elsevier, 1990. — PP. 633—672. Разборов, 2016, с. 3. Разборов, 2016, с. 8. Разборов, 2016, с. 9. Разборов, 2016, с. 22. Литература Разборов А. А. Алгебраическая сложность. — М.: МЦНМО, 2016. — 32 с. — ISBN 978-5-4439-1032-1.