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

(перенаправлено с «Класс VP»)

Алгебраическая сложность — раздел теории сложности вычислений, имеющий дело с полиномами. Был создан в основном благодаря работам Ф. Штрассена[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.

Литература

править
  • Разборов А. А. Алгебраическая сложность. — М.: МЦНМО, 2016. — 32 с. — ISBN 978-5-4439-1032-1.