Арифметические схемы более слабые, чем логические?

12

Пусть обозначает минимальный размер (немонотонной) арифметической схемы, вычисляющей заданный полилинейный многочлен и обозначают минимальный размер (немонотонной) логической схемы, логическую версию для определяется как: ( + , × , - ) е ( х 1 , ... , х п ) = Σ е Е с й п Π я = 1 х е я яA(f)(+,×,)B ( f ) ( , , ¬ )

f(x1,,xn)=eEcei=1nxiei,
B(f)(,,¬) е е Ь ( х 1 , ... , х п ) = е Е я : е я0 х яfbf
fb(x1,,xn)=eE i:ei0xi.
Известны ли полиномы для которых меньше, чем ? B ( f ) A ( f )fB(f)A(f)

Если мы рассмотрим монотонные версии схем - без минус и без Not вентилей - тогда может быть даже экспоненциально меньше, чем : возьмем, например, полином с кратчайшим st-путем на ; тогда и . Но что происходит в «немонотонном мире»? Конечно, большие промежутки не могут быть известны только потому, что у нас нет больших нижних оценок на . Но, может быть, есть хоть какие-то небольшие пробелы? ( ¬ ) B ( f )()(¬)B(f)A(f)fKnB(f)=O(n3)A(f)=2Ω(n)A(f)


ПРИМЕЧАНИЕ (15.03.2016) В моем вопросе я не указал, насколько большие коэффициенты . Игорь Сергеев вспомнил, что, например, следующий (одномерный) многочлен имеет (Штрассен и люди его группы). Но для этого многочлена, так как . Мы можем получить Фрон в многомерный полином из переменных с помощью использования подстановки Кронекера. Свяжите с каждым показателем моном , гдеcef(z)=j=1m22jmzjA(f)=Ω(m1/2)B(f)=0fb(z)=zff(x1,,xn)n=logmjXj=i:ai=1xi(a1,,an)являются 0-1 коэффициентами двоичного представления . Тогда желаемый многочлен имеет вид , и мы имеем, что Но логическая версия - это просто ИЛИ переменных, поэтому , и у нас есть четный экспоненциальный пробел. Таким образом, если величина коэффициентов может быть тройной экспоненциальной по числу переменных, то можно показать, что разрыв является даже экспоненциальным. (На самом деле, не сама величина - больше алгебраическая зависимость коэффициентов.) Вот почему реальная проблема с - это случай малыхjf=j=1mcjXj
A(f)+nA(f)=Ω(m1/2)=2Ω(n).
fB(f)n1nA(f)/B(f) A(f)коэффициенты (в идеале, только 0-1). Но в этом случае, как вспоминал Джошуа, нижняя граница Штрассена и Баура (с коэффициентами 0-1) остается лучшей из того, что мы имеем сегодня.A(f)=Ω(nlogn)

Стасис
источник

Ответы:

9

Казалось бы, перманент квалифицируется, по крайней мере, условно (то есть предполагается, что ). Обратите внимание, что булева версия перманента просто решает, имеет ли данный двудольный граф идеальное соответствие, имеющее многоразмерные схемы.VP0VNP0

[Обобщая комментарии ниже:] Несмотря на то, что этот пример является условным, на данный момент безоговорочно не следует ожидать ничего, кроме логарифмического разрыва, поскольку по-прежнему является самой известной нижней границей для общих алгебраических схем. Как указал Стасис, этот логарифмический пробел достигается функцией (требуются алгебраические схемы размера по Бауру-Штрассену), чей булевский тип версия просто .Σ п я = 1 х н я Ом ( п войти п ) х 1х 2х пΩ(nlogn)i=1nxinΩ(nlogn)x1x2xn

Джошуа Грохов
источник
Привет Джошуа: ты прав, постоянный пример (хотя и условный)! Ну, мы не знаем никакой нижней границы A (f) для перманента. Но если версии VP и VNP без констант отличаются, то мы знаем разделение B (f) и A (f), не зная (фактическую) границу.
Стасис
2
Ω(nlogn)
1
у Иисуса Навина: верно, опять хорошо. Если f является суммой n-й степени всех n одиночных переменных, то B (f) не больше n, и Баур-Штрассен показывает, что A (f) по крайней мере примерно в n раз логарифм от n. Это самый известный для A (f). Итак, самый большой из известных явных пробелов в моем вопросе действительно только логарифмический. (Вопрос в стороне: знаете ли вы, почему мой @ всегда исчезает в комментариях?)
Stasys
@Stasys: Хороший пример. (Re: в сторону. Я не делаю. Я думаю, что система делает некоторый автоматический вывод о том, кому что-то «назначено», и если вы направляете сообщение «человеку по умолчанию», то оно удаляет его. Я думаю, .)
Джошуа Грохов
Правильно. Автор сообщения всегда уведомляется о новых комментариях, поэтому система удаляет явное @ уведомление как избыточное.
Эмиль Йержабек