Сложность арифметической схемы

В сложности вычислений теории арифметические схемы являются стандартной моделью вычисления полиномов . Неформально, арифметическая схема принимает на вход либо переменные, либо числа, и ей разрешено либо складывать, либо умножать два выражения, которые она уже вычислила. Арифметические схемы предоставляют формальный способ понять сложность вычисления полиномов. Основной тип вопросов в этом направлении исследований: «Каков наиболее эффективный способ вычисления заданного полинома?» $f$?"

Определения

Простая арифметическая схема.

Арифметическая схема $C$ над полем $F$ и набор переменных $x_{1},\ldots ,x_{n}$ является ориентированным ациклическим графом следующим образом. Каждый узел в нем с нулевой степенью называется входным вентилем и помечен либо переменной $x_{i}$ или элемент поля в $F.$ Все остальные ворота помечены либо $+$ или $\times ;$ в первом случае это вентиль суммы , а во втором — вентиль произведения . Арифметическая формула — это схема, в которой каждый элемент имеет исходящую степень единицу (поэтому лежащий в ее основе граф представляет собой ориентированное дерево ).

Схема имеет две связанные с ней меры сложности: размер и глубину. Размер схемы схемы — это количество элементов в ней, а глубина — длина самого длинного направленного пути в ней. Например, схема на рисунке имеет размер шесть и глубину два.

Арифметическая схема вычисляет полином следующим естественным способом. Входной вентиль вычисляет полином, которым он помечен. Суммарные ворота $v$ вычисляет сумму полиномов, вычисленных его дочерними элементами (вентиль $u$ является ребенком ​ $v$ если направленное ребро $(v,u)$ есть на графике). Гейт продукта вычисляет произведение полиномов, вычисленных его дочерними элементами. Рассмотрим, например, схему на рисунке: входные элементы вычисляют (слева направо) $x_{1},x_{2}$ и $1,$ Суммарные элементы вычисляют $x_{1}+x_{2}$ и $x_{2}+1,$ и элемент продукта вычисляет $(x_{1}+x_{2})x_{2}(x_{2}+1).$

Обзор

Учитывая полином $f,$ мы можем спросить себя, как лучше всего это вычислить — например, каков наименьший размер вычислительной схемы? $f.$ Ответ на этот вопрос состоит из двух частей. Первая часть — найти схему , которая вычисляет $f;$ эту часть обычно называют верхней границей сложности $f.$ Вторая часть показывает, что ни одна другая схема не может добиться большего; эта часть называется нижней границей сложности $f.$ Хотя эти две задачи тесно связаны, доказательство нижних оценок обычно сложнее, поскольку для доказательства нижней границы нужно рассуждать обо всех схемах одновременно.

Обратите внимание, что нас интересует формальное вычисление полиномов, а не функции, которые определяют полиномы. Например, рассмотрим полином $x^{2}+x;$ над полем из двух элементов этот многочлен представляет нулевую функцию, но не является нулевым многочленом. В этом одно из отличий изучения арифметических схем от изучения булевых схем . В булевой сложности нас больше всего интересует вычисление функции, а не ее некоторое представление (в нашем случае представление в виде многочлена). Это одна из причин, по которой булева сложность сложнее арифметической. Изучение арифметических схем можно также рассматривать как один из промежуточных шагов на пути к изучению булевого случая. что мы едва понимаем.

Верхние границы

В рамках исследования сложности вычисления полиномов были найдены несколько хитроумных схем (альтернативных алгоритмов). Хорошо известным примером является алгоритм Штрассена для матричного произведения . Простой способ вычисления произведения двух $n\times n$ матрицы требуют схемы порядка размера $n^{3}.$ Штрассен показал, что на самом деле мы можем перемножить две матрицы, используя схему размером примерно $n^{2.807}.$ Основная идея Штрассена — это умный способ умножения $2\times 2$ матрицы. Эта идея является отправной точкой лучшего теоретического способа умножения двух матриц , который занимает примерно время. $n^{2.376}.$

одна интересная история связана с вычислением определителя Еще $n\times n$ матрица. Наивный способ вычисления определителя требует схем размером примерно $n!.$ Тем не менее мы знаем, что существуют схемы полиномиального размера по $n$ для вычисления определителя. Однако эти схемы имеют глубину, линейную по $n.$ Берковиц придумал усовершенствование: схему с полиномом размера $n,$ но глубины $O(\log ^{2}(n)).$

Мы также хотели бы упомянуть лучшую трассу, перманентом известную $n\times n$ матрица. Что касается определителя, то наивная схема перманента имеет размер примерно $n!.$ Однако для постоянного тока лучшая известная схема имеет размер примерно $2^{n},$ что определяется формулой Райзера: для $n\times n$ матрица $X=(x_{i,j}),$

$\operatorname {perm} (X)=(-1)^{n}\sum _{S\subseteq \{1,\ldots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}x_{i,j}$

(это схема глубины три).

Нижние границы

С точки зрения доказательства нижних оценок наши знания очень ограничены. Поскольку мы изучаем вычисление формальных многочленов, мы знаем, что многочлены очень большой степени требуют больших схем, например, многочлен степени $2^{2^{n}}$ нужна схема размером примерно $2^{n}.$ Итак, основная цель — доказать нижнюю оценку для многочленов малой степени, скажем, многочлена от $n.$ Фактически, как и во многих областях математики, аргументы подсчета говорят нам, что существуют полиномы полиномиальной степени, для которых требуются схемы суперполиномиального размера. Однако эти аргументы подсчета обычно не улучшают наше понимание вычислений. Следующая задача является основной открытой проблемой в этой области исследований: найти явный полином полиномиальной степени, требующий схем суперполиномиального размера .

Уровень техники представляет собой $\Omega (n\log d)$ нижняя граница размера схемных вычислений, например, полином $x_{1}^{d}+\cdots +x_{n}^{d}$ данные Штрассеном и Бауром и Штрассеном. Точнее, Штрассен использовал теорему Безу, чтобы показать, что любая схема, одновременно вычисляющая $n$ полиномы $x_{1}^{d},\ldots ,x_{n}^{d}$ имеет размер $\Omega (n\log d),$ а позже Баур и Штрассен показали следующее: дана арифметическая схема размером $s$ вычисление полинома $f,$ можно построить новую схему размером не более $O(s)$ который вычисляет $f$ и все $n$ частные производные $f.$ Поскольку частные производные $x_{1}^{d}+\cdots +x_{n}^{d}$ являются $dx_{1}^{d-1},\ldots ,dx_{n}^{d-1},$ нижняя граница Штрассена применима к $x_{1}^{d}+\cdots +x_{n}^{d}$ также. Это один из примеров, когда некоторая верхняя граница помогает доказать нижние границы; конструкция схемы, предложенная Бауром и Штрассеном, подразумевает нижнюю оценку для более общих полиномов.

Отсутствие возможности доказать нижние оценки заставляет нас рассматривать более простые модели вычислений. Вот некоторые примеры: монотонные схемы (в которых все элементы поля представляют собой неотрицательные действительные числа), схемы постоянной глубины и полилинейные схемы (в которых каждый элемент вычисляет полилинейный полином ). Эти ограниченные модели были тщательно изучены, и было получено некоторое понимание и результаты.

Алгебраические P и NP

Наиболее интересной открытой проблемой в теории сложности вычислений является проблема P и NP . Грубо говоря, эта проблема заключается в том, чтобы определить, можно ли решить данную проблему так же легко, как можно показать, что решение данной проблемы существует. В своей основополагающей работе «Валиант» предложил алгебраический аналог этой проблемы - проблему VP vs. VNP .

Класс VP является алгебраическим аналогом P; это класс полиномов $f$ полиномиальной степени, которые имеют схемы полиномиального размера над фиксированным полем $K.$ Класс VNP является аналогом NP. VNP можно рассматривать как класс полиномов. $f$ полиномиальной степени такой, что по данному моному можно определить его коэффициент в $f$ эффективно, со схемой полиномиального размера.

Одним из основных понятий теории сложности является понятие полноты . Учитывая класс полиномов (таких как VP или VNP), полный полином $f$ поскольку этот класс является многочленом с двумя свойствами: (1) он является частью класса и (2) любой другой многочлен $g$ в классе легче, чем $f,$ в том смысле, что если $f$ имеет небольшую схему, то и она тоже $g.$ Валиант показал, что перманент полный для класса ВНП. Итак, чтобы показать, что VP не равно VNP, нужно показать, что перманент не имеет схем полиномиального размера. Это остается нерешенной открытой проблемой.

Уменьшение глубины

Одним из ориентиров в нашем понимании вычисления полиномов является работа Валианта, Скайума, Берковица и Ракоффа. Они показали, что если полином $f$ степени $r$ имеет схему размером $s,$ затем $f$ также имеет схему полиномиального размера по $r$ и $s$ глубины $O(\log(r)\log(s)).$ Например, любой полином степени $n$ который имеет схему полиномиального размера, также имеет схему полиномиального размера глубины примерно $\log ^{2}(n).$ Этот результат обобщает схему Берковица на любой полином полиномиальной степени, который имеет схему полиномиального размера (например, определитель). Аналог этого результата в булевой настройке считается ложным.

Одним из следствий этого результата является моделирование цепей с помощью относительно небольших формул, формул квазиполиномиального размера: если многочлен $f$ степени $r$ имеет схему размером $s,$ тогда у него есть формула размера $s^{O(\log(r))}.$ Это моделирование проще, чем уменьшение глубины Valiant el al. и был показан ранее Хиафилом.

См. также

• Полиномиальная оценка для более общего и менее формального обсуждения сложности полиномиальной оценки.

Дальнейшее чтение

• Бюргиссер, Питер (2000). Полнота и редукция в теории алгебраической сложности . Алгоритмы и вычисления в математике. Том. 7. Берлин: Шпрингер-Верлаг . ISBN  978-3-540-66752-0 . Збл   0948.68082 .
• Бюргиссер, Питер; Клаузен, Майкл; Шокроллахи, М. Амин (1997). Алгебраическая теория сложности . Основные принципы математических наук. Том 315. При сотрудничестве Томаса Ликтейга. Берлин: Springer Verlag . ISBN  978-3-540-60582-9 . Збл   1087.68568 .
• фон зур Гатен, Иоахим (1988). «Алгебраическая теория сложности». Ежегодный обзор компьютерных наук . 3 : 317–347. doi : 10.1146/annurev.cs.03.060188.001533 .