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