Открыть главное меню

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

ОпределениеПравить

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

ЛитератураПравить