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

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

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

Определение

Алгебраической сложностью полинома , которую обозначают через , называется длина кратчайшей неветвящейся программы, вычисляющей [4]. Неветвящейся программой называется последовательность функций , определённая следующим образом:

,
,

где и  — полиномы первой степени. Длиной неветвящейся программы называется число членов в последовательности . Неветвящаяся программа длиной вычисляет полином , если .

Свойства

  • Существует полином степени от одной переменной, алгебраическая сложность которого не меньше .

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

  • Неизвестны нетривиальные нижние и верхние оценки алгебраической сложности частичных сумм разложения функции в ряд . Существует гипотеза, что для вычисления первых n слагаемых этого ряда требуется выполнить умножений[5].
  • Неизвестны нетривиальные нижние и верхние оценки алгебраической сложности частичных сумм разложения функции в ряд .

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

Определение

Рассмотрим операцию умножения квадратной матрицы с постоянными элементами: на вектор .

Аддитивной сложностью квадратной матрицы называется длина самой короткой последовательности функций , вычисляющих произведение вектора на строку таблицы и определённых следующим образом: , ...,, ... где , а являются постоянными.

Свойства

Класс VP

Классом VP называется множество всех семейств полиномов , для которых . Например, задача вычисления детерминанта матрицы принадлежит классу VP. Класс сложности вычислений VP является алгебраическим аналогом класса P из теории сложности вычислений[6].

Класс VNP

Класс VNP включает в себя семейство полиномов , если для него найдется семейство полиномов из класса VP такое, что выполнено равенство . Суммирование ведется по всем векторам из нулей и единиц длины , а равно значению -й координаты вектора e. Например, задача вычисления перманента матрицы принадлежит классу VNP. Класс сложности вычислений VNP является алгебраическим аналогом класса NP из теории сложности вычислений.

Примечания

  1. Strassen, V., Vermeidung von Divisionen, Crelles J.Reine Angew. Math 264, 1973, 184-202.
  2. Strassen V. Algebraic Complexity Theory // Handbook of theoretical computer science. — Amsterdam: Elsevier, 1990. — PP. 633—672.
  3. Разборов, 2016, с. 3.
  4. Разборов, 2016, с. 8.
  5. Разборов, 2016, с. 9.
  6. Разборов, 2016, с. 22.

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.