Русская Википедия:Алгебраическая сложность
Алгебраическая сложность — раздел теории сложности вычислений, имеющий дело с полиномами. Был создан в основном благодаря работам Ф. Штрассена[1][2]Шаблон:Sfn.
Алгебраическая сложность полинома
Определение
Алгебраической сложностью полинома <math>f</math>, которую обозначают через <math>L(f)</math>, называется длина кратчайшей неветвящейся программы, вычисляющей <math>f</math>Шаблон:Sfn. Неветвящейся программой называется последовательность функций <math>f_{1}, ..., f_{i}, ...</math>, определённая следующим образом:
- <math>f_{1}=A_{1}(x_{1}, ..., x_{k})B_{1}(x_{1}, ..., x_{k})</math>,
- …
- <math>f_{i}=A_{i}(x_{1}, ..., x_{k}, f_{1}, ..., f_{i-1})B_{i}(x_{1}, ..., x_{k}, f_{1}, ..., f_{i-1})</math>,
- …
где <math>A</math> и <math>B</math> — полиномы первой степени. Длиной неветвящейся программы называется число членов в последовательности <math>f_{1}, ..., f_{i}, ...</math>. Неветвящаяся программа длиной <math>m</math> вычисляет полином <math>p</math>, если <math>f_{m}=p</math>.
Свойства
- Существует полином степени <math>n</math> от одной переменной, алгебраическая сложность которого не меньше <math>\Omega (\sqrt{n})</math>.
Нерешённые проблемы
- Неизвестны нетривиальные нижние и верхние оценки алгебраической сложности частичных сумм разложения функции в ряд <math>e^{x} \sim 1+x+\frac{x^{2}}{2}+\ldots+\frac{x^{n}}{n!}</math>. Существует гипотеза, что для вычисления первых n слагаемых этого ряда требуется выполнить <math>\Omega (n)</math> умноженийШаблон:Sfn.
- Неизвестны нетривиальные нижние и верхние оценки алгебраической сложности частичных сумм разложения функции в ряд <math>\ln(1-x) \sim -x-\frac{x^{2}}{2}-\ldots-\frac{x^{n}}{n!}</math>.
Аддитивная сложность матрицы
Определение
Рассмотрим операцию умножения квадратной матрицы с постоянными элементами: <math>\begin{pmatrix} a_{11} & a_{12} & ... & a_{1n} \\ ... & ... & ... & ... \\ a_{n1} & a_{n2} & ... & a_{nn} \end{pmatrix}</math> на вектор <math>x=(x_{1}, ..., x_{n})</math>.
Аддитивной сложностью квадратной матрицы <math>A</math> называется длина самой короткой последовательности функций <math>f_{1}, ..., f_{i}, ...</math>, вычисляющих произведение вектора <math>x</math> на <math>j</math> строку таблицы <math>A</math> и определённых следующим образом: <math>f_{1}=\alpha_{1}u_{1}+\beta_{1}v_{1}</math>, ...,<math>f_{i}=\alpha_{i}u_{i}+\beta_{i}v_{i}</math>, ... где <math>u_{i}, v_{i} \in \left \{ x_{1}, ..., x_{n}, f_{1}, ..., f_{i-1} \right \}</math>, а <math>\alpha_{i}, \beta_{i}</math> являются постоянными.
Свойства
- Аддитивная сложность произвольной матрицы равна <math>O(n^{2})</math>. У некоторых видов матриц она меньше. Например, у матрицы быстрого преобразования Фурье, она равна <math>O(n \log_{2} n)</math>.
Класс VP
Классом VP называется множество всех семейств полиномов <math>f_{n}</math>, для которых <math>L(f_{n}) \leqslant p(n)</math>. Например, задача вычисления детерминанта матрицы принадлежит классу VP. Класс сложности вычислений VP является алгебраическим аналогом класса P из теории сложности вычисленийШаблон:Sfn.
Класс VNP
Класс VNP включает в себя семейство полиномов <math>f_{n}(x_{1}, ..., x_{m(n)})</math>, если для него найдется семейство полиномов <math> \left \{ g_{n}(x_{1}, ..., x_{m(n)}, y_{1}, ..., y_{k(n)} ) \right \} </math> из класса VP такое, что выполнено равенство <math> 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)} ) </math>. Суммирование ведется по всем векторам <math>e</math> из нулей и единиц длины <math>k(n)</math>, а <math>e_{i}</math> равно значению <math>i</math>-й координаты вектора e. Например, задача вычисления перманента матрицы принадлежит классу VNP. Класс сложности вычислений VNP является алгебраическим аналогом класса NP из теории сложности вычислений.
Примечания
Литература
