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

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

Определения

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

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

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

Арифметическая схема вычисляет полином следующим образом. Входной вентиль вычисляет полином, которым он помечен. Суммарный вентиль вычисляет сумму многочленов, вычисленных его дочерними элементами (вентиль является дочерним элементом, если направленное ребро находится в графе). Элемент продукта вычисляет произведение многочленов, вычисленных его дочерними элементами. Рассмотрим схему на рисунке, например: входные ворота вычислить (слева направо) и ворота сумма вычислить и и продукт затвора вычисляет ${\ 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 х ^ {2} + х;}$

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

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

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

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

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

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

Нижние оценки

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

Уровень техники - это нижняя граница размера схемотехнических вычислений, например, полином, данный Штрассеном и Бауром и Штрассеном. Точнее, Штрассен использовал лемму Безу, чтобы показать, что любая схема, которая одновременно вычисляет многочлены, имеет размер, а позже Баур и Штрассен показали следующее: имея арифметическую схему размера , вычисляющую многочлен, можно построить новую схему размера не более, которая вычисляет и все частные производные от Поскольку частные производные от являются нижней границей Штрассена, также применяется к . Это один из примеров, когда верхняя оценка помогает в доказательстве нижней границы; построение схемы, данное Бауром и Штрассеном, влечет оценку снизу для более общих многочленов. ${\ Displaystyle \ Omega (п \ журнал d)}$ ${\ displaystyle x_ {1} ^ {d} + \ cdots + x_ {n} ^ {d}}$ ${\ displaystyle n}$ ${\ displaystyle x_ {1} ^ {d}, \ ldots, x_ {n} ^ {d}}$ ${\ displaystyle \ Omega (п \ журнал 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 vs. NP . Грубо говоря, эта проблема состоит в том, чтобы определить, может ли данная проблема быть решена так же легко, как можно показать, что решение существует для данной проблемы. В своей основополагающей работе Valiant предложил алгебраический аналог этой проблемы, проблему VP vs. VNP .

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

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

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

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

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

Смотрите также

Полиномиальное вычисление для более общего и менее формального обсуждения сложности полиномиального вычисления.

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

Бюргиссер, Питер (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. DOI : 10.1146 / annurev.cs.03.060188.001533 .

Languages

In other projects