Алгебраическая сложность — раздел теории сложности вычислений, имеющий дело с полиномами. Был создан в основном благодаря работам Ф. Штрассена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..
Алгебраическая сложность полинома
Определение Алгебраической сложностью полинома , которую обозначают через , называется длина кратчайшей неветвящейся программы, вычисляющей . Неветвящейся программой называется последовательность функций , определённая следующим образом: , … , … где и — полиномы первой степени. Длиной неветвящейся программы называется число членов в последовательности . Неветвящаяся программа длиной вычисляет полином , если .
Свойства Существует полином степени от одной переменной, алгебраическая сложность которого не меньше .
Нерешённые проблемы Неизвестны нетривиальные нижние и верхние оценки алгебраической сложности частичных сумм разложения функции в ряд . Существует гипотеза, что для вычисления первых n слагаемых этого ряда требуется выполнить умножений. Неизвестны нетривиальные нижние и верхние оценки алгебраической сложности частичных сумм разложения функции в ряд .
Аддитивная сложность матрицы
Определение Рассмотрим операцию умножения квадратной матрицы с постоянными элементами: на вектор .
Аддитивной сложностью квадратной матрицы называется длина самой короткой последовательности функций , вычисляющих произведение вектора на строку таблицы и определённых следующим образом: , ...,, ... где , а являются постоянными.
Свойства Аддитивная сложность произвольной матрицы равна . У некоторых видов матриц она меньше. Например, у матрицы быстрого преобразования Фурье, она равна .
Класс VP
Классом VP называется множество всех семейств полиномов , для которых . Например, задача вычисления детерминанта матрицы принадлежит классу VP. Класс сложности вычислений VP является алгебраическим аналогом класса P из теории сложности вычислений.
Класс VNP
Класс VNP включает в себя семейство полиномов , если для него найдется семейство полиномов из класса VP такое, что выполнено равенство . Суммирование ведется по всем векторам из нулей и единиц длины , а равно значению -й координаты вектора e. Например, задача вычисления перманента матрицы принадлежит классу VNP. Класс сложности вычислений VNP является алгебраическим аналогом класса NP из теории сложности вычислений.
Примечания
Литература
Категория:Теория сложности вычислений Категория:Многочлены