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

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

Определения

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

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

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

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

Обзор

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

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

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

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

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

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

{displaystyle operatorname {perm} (X) = (- 1) ^ {n} sum _ {Ssubseteq {1, ldots, n}} (- 1) ^ {| S |} prod _ {i = 1} ^ {n } сумма _ {jin S} x_ {i, j}}

(это контур глубины три).

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

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

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

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

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

Самая интересная открытая проблема в теории сложности вычислений - это P против NP проблема. Грубо говоря, эта проблема состоит в том, чтобы определить, может ли данная проблема быть решена так же легко, как можно показать, что решение существует для данной проблемы. В своей основополагающей работе Valiant^[3] предложил алгебраический аналог этой проблемы, VP против VNP проблема.

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

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

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

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

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

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

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

Сноски

^ Л. Г. Валиант. Почему сложная теория булевой сложности? Труды симпозиума Лондонского математического общества по сложности булевых функций, стр. 84–94, 1992.
^ С. Дж. Берковиц. При вычислении определителя за малое параллельное время с использованием небольшого количества процессоров. Инф. Prod. Letters 18, pp. 147–150, 1984.
^ Л. Г. Валиант. Классы полноты в алгебре. В Proc. 11-го ACM STOC, стр. 249–261, 1979.
^ Л. Г. Валиант, С. Скайум, С. Берковиц, К. Ракофф. Быстрое параллельное вычисление многочленов с использованием нескольких процессоров. SIAM J. Comput. 12 (4), стр. 641–644, 1983.
^ Л. Хяфил. О параллельном вычислении многомерных многочленов. SIAM J. Comput. 8 (2), стр. 120–123, 1979.

[1] Л. Г. Валиант. Почему сложная теория булевой сложности? Труды симпозиума Лондонского математического общества по сложности булевых функций, стр. 84–94, 1992.

[2] С. Дж. Берковиц. При вычислении определителя за малое параллельное время с использованием небольшого количества процессоров. Инф. Prod. Letters 18, pp. 147–150, 1984.

[3] Л. Г. Валиант. Классы полноты в алгебре. В Proc. 11-го ACM STOC, стр. 249–261, 1979.

[4] Л. Г. Валиант, С. Скайум, С. Берковиц, К. Ракофф. Быстрое параллельное вычисление многочленов с использованием нескольких процессоров. SIAM J. Comput. 12 (4), стр. 641–644, 1983.

[5] Л. Хяфил. О параллельном вычислении многомерных многочленов. SIAM J. Comput. 8 (2), стр. 120–123, 1979.

[1]

[2]

[3]

[4]

[5]