Сложность тестирования значения по сравнению с вычислением функции

36

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

Оценка перманента неотрицательной целочисленной матрицы является # P-сложной, но при этом указывается, является ли такой перманент нулевым или ненулевым в P (двудольное сопоставление)
Существует n действительных чисел , таких что многочлен имеет следующие свойства (в действительности большинство наборов из действительных чисел будут иметь эти свойства) , Для заданного входного значения проверка того, равен ли этот полином нулю, требует умножения и сравнения (по результату Бен-Ор , поскольку в нулевом множестве компонентов), но для оценки приведенного выше полинома требуется как минимум шаги, Патерсон-Стокмейер . $a_1,...,a_n$ $\prod_{i=1}^{n}(x - a_i)$ $n$ $x$ $\Theta(\log n)$ $n$ $\Omega(\sqrt{n})$
Для сортировки требуются шаги в дереве сравнения (также шаги в реальном алгебраическом дереве решений, опять же по результату Бен-Ор), но при проверке сортировки списка используются только сравнений. $\Omega(n \log n)$ $\Omega(n \log n)$ $n-1$

Существуют ли общие условия для полинома, достаточные для того, чтобы подразумевать, что (алгебраическая) сложность проверки, является ли полином нулевым, эквивалентна сложности вычисления полинома?

Я ищу условия, которые не зависят от знания сложности проблем заранее.

( Пояснение 27.10.2010 ) Чтобы было ясно, полином не является частью ввода. Это означает, что, учитывая фиксированное семейство функций (по одной для каждого размера ввода (либо длины битов, или количества входов)), я хочу сравнить сложность проблемы языка / решения со сложностью оценки функций . $\{ f_n \}$ $\{ X : f_n(X) = 0 \text{ where } n \text{ is the "size" of } X \}$ $\{f_n\}$

Пояснение: я спрашиваю об асимптотической сложности оценки / тестирования семейств полиномов. Например, над фиксированным полем (или кольцом, таким как ) «перманент» - это не один многочлен, а бесконечное семейство где является перманентом матрицы над этим полем (или кольцом). $\mathbb{Z}$ $\{perm_{n} : n \geq 0 \}$ $perm_{n}$ $n \times n$

cc.complexity-theory reference-request algebraic-complexity Джошуа Грохов
источник

Разве ответ на ваш вопрос не зависит не только от самого полинома, но и от его представления?

Ильяраз

@ilyaraz: Не уверен, что вы имеете в виду. Полином не является частью ввода.

Арнаб

Джошуа, можешь ли ты «латексизировать» вопрос для лучшей читабельности?

Суреш Венкат

4

Я нашел статью Валианта ( dx.doi.org/10.1016/0020-0190(76)90097-1 ) «Относительная сложность проверки и оценки», в которой рассматривается, по сути, тот же вопрос, но в стандартной настройке машины Тьюринга, а не алгебраическая установка. Он не отвечает на мой вопрос, но если вы нашли этот вопрос интересным, вы могли бы также найти его статью интересной.

Джошуа Грохов

1

«Алгоритмическое использование теоремы Фефермана – Вота» Маковского, возможно, имеет отношение к делу. Он определяет полиномы суммированием по MSOL-определяемым структурам на графах и показывает, что их легко оценить, когда графы ограничены по ширине дерева

Ярослав Булатов,

4

Над тестирование на ноль и вычисление «почти» одинаково в следующем смысле: Предположим, у вас есть дерево решений, которое проверяет, является ли ненулевой неприводимый многочлен ненулевым. Мы работаем над , поэтому мы можем только проверить на равенство, но у нас нет «<». Это важное отличие от второго примера в вопросе! Теперь возьмем типичный путь, т. Е. Путь, по которому идут почти все входные данные (мы всегда следуем ветке " "). Кроме того, возьмем типичный путь всех элементов в многообразии . Пусть будет узлом, в котором эти два пути впервые принимают разные ветви. Пусть $\mathbb{C}$ $f$ $\mathbb{C}$ $\not=$ $V(f)$ $v$ $h_1,\dots,h_m$ быть полиномами, которые проверяются по общему префиксу двух путей. Поскольку замкнуто, все элементы, лежащие в и достигающие также лежат в . Следовательно, если , то один из обращается в нуль на . Мы применяем Nullstellensatz Гильберта к и получаем, что для некоторого многочлена который взаимно прост с . Короче говоря, пока мы не вычисляем , при решении, будет ли , мы должны вычислить для некоторого взаимно простого $V(f)$ $V(f)$ $v$ $V(h_m)$ $f(x) = 0$ $h_i$ $x$ $h_1 \cdots h_m$ $f g = h_1 \cdots h_m$ $g$ $f$ $f$ $f(x) = 0$ $fg$ $g$ ,

Маркус Блезер
источник

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

f (x) = 0

$f(x)=0$

f g

$fg$

f

$f$

f

$f$

f g

$fg$

f g

$fg$

f

$f$

f (x) = 0

$f(x)=0$

d e g f

$deg f$

g

$g$

Джошуа Грохов

Я не понимаю: если вы можете оценить , то вы можете проверить на ноль с помощью еще одной операции, а именно, одного теста на равенство в конце. Что может пойти не так, так это то, что оценка дешевле, чем оценка по какой-то причине. (Примечание: оценка означает оценку в общей точке, то есть в неопределенной точке.)

f

$f$

f g

$fg$

f

$f$

f

$f$

Маркус Блезер

Точно. Оценка может быть проще, чем оценка . (Я знаю, что оценка означает оценку в общей точке; я не совсем понимаю, почему вы думали, что ваше последнее замечание в скобках было необходимо, но это может быть помимо сути.) Что именно вы не получаете? Основываясь на вашем последнем комментарии, я бы сказал, что мы оба понимаем ситуацию и согласны с пониманием друг друга ... См. Также «Сложность факторов многомерных полиномов» Бургиссера, которая дает тот же вывод, который я высказал в своем предыдущем комментарии.

f g

$fg$

f

$f$

f

$f$

Джошуа Грохов

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

Джошуа Грохов

Извините, я неправильно понял ваш первый комментарий. Все хорошо.

Маркус Блезер

5

«Алгоритмическое использование теоремы Фефермана – Vaught» Маковского, возможно, имеет значение. Он определяет полиномы путем суммирования по MSOL-определяемым структурам на графах и показывает, что их можно оценить, когда графы ограничены по ширине дерева.

Это не говорит о разнице в сложности тестирования / оценки, помимо того, что FPT. Проверка значения означает, что необходимо задавать вопрос о том, существует ли набор переменных, такой, что данная формула MSO2 на данном графике оценивается как true, тогда как оценка включает перечисление по удовлетворяющим назначениям формулы MSO2. Похоже, это связано с вопросом о том, как сложность подсчета SAT связана со сложностью SAT.

Редактировать 10/29 Еще одной полезной концепцией может быть рассмотрение свойства «Унифицированная сложная точка». Очевидно, что многочлены с этим свойством либо легко оценить во всех точках, либо трудно оценить почти в каждой точке. Маковски дает некоторые ссылки на слайды 46-52 - http://www.cs.technion.ac.il/admlogic/TR/2009/icla09-slides.pdf

Ярослав Булатов
источник

3

Я рискну предположить, что оценка полинома в для фиксированного простого числа (или любого его конечного расширения поля и с коэффициентами, ограниченными одним и тем же полем) будет соответствовать вашему критерию. $q(x)$ $\mathbb F_p$ $p$

более конкретно, давайте рассмотрим полином из . Мы знаем, что в , поэтому, если мы предположим, что любой многочлен уже находится в сокращенной форме, если задан в качестве входных данных, нам остается просто рассмотреть один из: и соответственно оценка любого из этих многочленов в или занимает не более 2 арифметических операций. $\mathbb F_2[x]$ $x^2=x$ $\mathbb F_2$ $0,1,x,x+1$ $0$ $1$

Я полагаю, что подобное утверждение «постоянное время через фиксированное число арифметических операций» применяется в более общем случае для где где простое число. обратите внимание, что если не является фиксированным, это утверждение больше не является действительным $\mathbb F_q$ $q=p^n$ $p$ $n$

Картер Тацио Шонвальд
источник

1

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

{p e r m_{n} : n \geq 0}

$\{perm_{n} : n \geq 0\}$

p e r m_{n}

$perm_{n}$

n \times n

$n \times n$

Джошуа Грохов

1

Справедливости ради, давайте проясним формулировку вопроса с помощью «многочленов в бесконечном поле», а не понизим попытку ответа, которая указывает на необходимое уточнение :) Ваш пример с перманентом не делает это очевидным, потому что матрицы по-прежнему более чем фиксированы кольцо или поле. Кроме того, в случае я на самом деле не ограничиваю себя рассмотрением только этих 4 полиномов, а скорее использую отношение эквивалентности для уменьшения любого полинома более высокой степени до одного из этих четырех по времени, линейного в степень полинома.

F_{2}

$\mathbb F_2$

x^{2} = x

$x^2=x$

Картер Тацио Шонвальд

1

Картер: Я думал, что было ясно, что я спрашивал об асимптотике, но теперь я уточнил. Вы также можете использовать поливарию, где число переменных не фиксировано. Извините за понижение голосов, но я не думаю, что вы заслуживаете половину награды (+25) за то, что указали, что конечные наборы 1-var polys могут быть оценены с O (1) ops. Я знаю, что вы на самом деле указывали на что-то менее очевидное, но это не имело отношения к вопросу: как уже указывалось в комментариях к Q , поли не является частью ввода. Таким образом, для F_2 действительно нужно рассмотреть только 4 1-var-полиса (использование x ^ 2 = x не нужно).

Джошуа Грохов

хм, ваше разъяснение все еще не работает, вам нужно иметь фиксированное кольцо или поле для или его бессмыслицы.

p e r m_{n}

$perm_n$

Картер Тацио Шонвальд

1

Я согласен с вами в целом, поэтому я исправил уточнение. Интересно, что в случае многочленов с коэффициентами 0,1, -1 (таких как perm и det), разрешение изменять поле не является полной чепухой. Можно представить себе такой результат, как: « , ли 0», так же сложно, как оценить помощью более »(для некоторой указанной последовательности из простых сил, не обязательно все одинаковые характеристики). Правда, это не будет таким естественным результатом, как над фиксированным полем.

d e t_{n}

$det_{n}$

d e t_{n}

$det_{n}$

F_{p_{n}}

$\mathbb{F}_{p_{n}}$

p_{n}

$p_{n}$

Джошуа Грохов

3

Я не уверен, правильно ли я понимаю вопрос, но позвольте мне попытаться пролить свет.

Как правило, оценка полинома при определенных значениях проще, чем проверка идентичности, особенно когда представление полинома осуществляется через схему (некоторое сжатое представление). Тем не менее, существует множество рандомизированных алгоритмов тестирования идентичности ( Schwarz-Zippel - самый простой), который работает только на оценках.

В некоторых особых случаях у нас есть тесты «черного ящика» для проверки идентичности, где вы можете проверить, равен ли полином нулю или нет, просто оценив его по заранее определенному набору точек. Простым примером этого является случай, когда многочлен является «разреженным» (просто имеет одночленов). Чтобы упростить изложение, предположим, что многочлен является мультилинейным (каждый одночлен является произведением различных переменных). $n^{O(1)}$

Естественным способом отправки многомерного полилинейного полинома в одномерный вариант является замена . В результате получается многочлен, скажем, . Конечно, это может быть полином экспоненциальной степени, но давайте перейдем по модулю для небольшого диапазона . Теперь a будет «плохим» для пары мономов, если и отображаются на один и тот же моном по модулю . Или, другими словами, делит . Таким образом, пока не делит $x_i \mapsto y^{2^i}$ $\sum_{i\in S} \alpha_i y^{a_i}$ $y^r - 1$ $r$ $r$ $y^a$ $y^b$ $y^r - 1$ $r$ $a - b$ $r$ $\prod_{i,j\in S} (a_i - a_j)$ этого бы не случилось Следовательно, достаточно пробегать полиномиальный диапазон 's. Таким образом, достаточно оценить многочлен на некоторых корнях единиц, и мы можем выяснить, равен ли он многочлену или нет. $r$

Был достигнут больший прогресс в алгоритмах проверки идентичности черного ящика. Прямо сейчас большинство из них находятся на ограниченной глубине 3 контура (сумма произведений сумм переменных). (FWIW) Некоторые из них упоминаются более подробно в главах 3 и 4 моей диссертации . И в последнее время Саксена и Сешадри получили дальнейшие улучшения .

Ramprasad
источник

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

x

$x$

f (x) = 0

$f(x)=0$

x

$x$

f (x)

$f(x)$

Джошуа Грохов

Ах! Понятно ... Спасибо за разъяснения; мой ответ не слишком уместен в этом случае.

Рампрасад

1

Любая проблема #P или даже # P / poly может быть записана как полином: создайте схему из вентилей NAND, запишите их как где и - 0-1-значные целые числа, и суммируйте по всем входным данным. Это дает многочлен в для входных данных размера . Решением проблемы является проверка того, равно ли это 0. $1-xy$ $x$ $y$ $\mathbb{Z}[x_1,...,x_n]$ $n$

Колин Маккуиллан
источник

Да. Это немного более общая версия примера перманента. Такое решение проблемы есть в (или ). Считается, что значительно сложнее, чем (поскольку это так же сложно, как и вся полиномиальная иерархия). Вы знаете , общего состояния на проблем , которые, если они удовлетворены с помощью функции подразумевает , что не сложнее , чем ее решения версии?

N P

$NP$

N P / p o l y

$NP/poly$

# P

$\# P$

N P

$NP$

# P

$\# P$

# P

$\# P$

f

$f$

f

$f$

Джошуа Грохов

Существует предположение, что версии с естественным подсчетом NP-полных задач всегда # P-полны, но я не знаю других отношений. В некотором роде тривиальным условием было бы то, что задача является саморежимимой и f ограничена полиномом.

Колин Маккуиллан

Сложность тестирования значения по сравнению с вычислением функции

Ответы: