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

14

В К -й элементарный симметричный полином SКN(Икс1,...,ИксN) является суммой всех продуктов различных переменных. Меня интересует сложность монотонной арифметической схемы этого многочлена. Простой алгоритм динамического программирования (как и рис. 1 ниже) дает схему с воротами .(NК)К(+,×)(+,×)О(КN)

Вопрос: Известна ли нижняя граница ? Ω(КN)

цепи перекос , если по крайней мере один из двух входов каждого затвора продукта является переменной. Такая схема на самом деле такая же, как сеть с коммутацией и выпрямлением (ориентированный ациклический граф с некоторыми ребрами, помеченными переменными; каждый st-путь дает произведение своих меток, а результат представляет собой сумму по всем st-путям). Уже 40 лет назад Марков доказал удивительно жесткий результат: минимальная монотонная арифметическая схема для имеет ровно . Верхняя оценка следует из фиг.1.: (+,×)SКN k(nk+1)введите описание изображения здесь

Но я не видел ни одной попытки доказать такую ​​нижнюю оценку для нескошенных цепей. Это только наше «высокомерие», или есть какие-то присущие трудности, встречающиеся на этом пути?

PS Я знаю, что ворота необходимы для одновременного вычисления всех . Это следует из нижней границы размера монотонных логических схем, сортирующих вход 0-1; см. стр. 158 книги Инго Вегенера . АКС сортировка сети также подразумевает , что ворота достаточно в этом (логическое) случае. На самом деле Баур и Штрассен доказали тесную связь с размером немонотонной арифметической схемы для . Но как насчет монотонных арифметических схем?S n 1 , , S n n O ( n log n ) Θ ( n log n ) S n n / 2Ω(nlogn)S1n,,SnnO(nlogn)Θ(nlogn)Sn/2n

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

Ответы:

6

Одна из проблем в том , что если убрать «монотонный» ограничение, мы действительно знаем , как эффективно вычислять такие вещи. Вы можете вычислить значение всех (вычислить все n + 1 элементарных симметрических полиномов) за O ( n log 2 n ) времени, используя полиномиальное умножение на основе FFT. Таким образом, доказательство нижней границы Ω ( n k ) в модели монотонной схемы потребует доказательства Ω ( n 2 )S0n,,Snnn+1O(nlog2n)Ω(nk)Ω(n2) нижняя оценка умножения полиномов.

Вот как. Введем формальное неизвестное и рассмотрим полиномy

P(y)=i=1n(1+xiy).

Обратите внимание, что поскольку являются известными константами, это одномерный многочлен с неизвестным y и степенью n . Теперь вы можете заметить, что коэффициент y k в P ( y ) в точности равен S n k , поэтому для оценки всех S n 0 , , S n n достаточно вычислить P ( y ) .xiynykP(y)SknS0n,,SnnP(y)

Это позволяет вычислить за O ( n lg 2 n ) времени: построить сбалансированное двоичное дерево многочленов с ( 1 + x i y ) на листьях и умножить многочлены. Умножение двух полиномов степени d занимает время O ( d lg d ) с использованием методов БПФ, поэтому мы получаем повторение T ( n ) = 2 T ( n / 2 ) +P(y)O(nlg2n)(1+xiy)dO(dlgd) , который решает до T ( n ) = O ( n lg 2 n ) . Для удобства я игнорирую поли ( LG LG N ) факторы.T(n)=2T(n/2)+O(nlgn)T(n)=O(nlg2n)poly(lglgn)

Если вам небезразличен случай, когда очень мало, вы можете вычислить S n 0 , , S n k за O ( n lg 2 k ) времени, используя аналогичные приемы, имея в виду, что вы заботитесь только о P ( x ) mod y k + 1 (т. е. отбрасывая все члены y k + 1 или более высокие степени y ).kS0n,,SknO(nlg2k)P(x)modyk+1yk+1y

Конечно, БПФ использует вычитание, поэтому наивно это не выражается в монотонной схеме. Я не знаю, есть ли какой-то другой способ эффективного умножения полиномов с монотонными арифметическими схемами, но любой эффективный монотонный метод умножения полиномов немедленно приводит к алгоритму для вашей задачи. Таким образом, нижние оценки для вашей задачи требуют / подразумевают более низкие оценки для умножения полиномов.

DW
источник
2
DW, спасибо за отзыв об этой конструкции! Это обычно приписывают Бен-Ору, и я должен был упомянуть это. Конструкция также дает <i> формулу </ i> размера и глубины только 3 (!) Для вычисления оператора S n 0 , , S n n (путем вычисления P ( y ) при некотором n + 1O(n2)3S0n,,SnnP(y)n+1точки). Это использовалось для разделения однородных и неоднородных формул малой глубины. Но, как вы упоминаете, конструкция в значительной степени использует вычитание. Итак, мой вопрос: насколько «существенным» является это использование? Это может быть интересно и в сценарии с ограниченной глубиной.
Стасис
3
@Stasys: Я думаю, что вычитание довольно важно. А именно нижняя граница Нисана-Вигдерсона на глубину 3 однородных контура; в схемах с однородной глубиной 3 смысл в том, что вычислять члены, степени которых отличаются от степени вывода, бесполезно. Так что это ограничивает виды отмены, которые могут произойти. Принимая во внимание, что в конструкции Бен-Ор для вычисления необходимо вычислить многочлен степени n (даже если выход имеет степень k < n ), а затем критически использовать отмену, чтобы избавиться от членов степеней > k , Это не доказательство, просто какая-то интуиция ...Sknnk<n>k
Джошуа Грохов
@ Джошуа: да, мы знаем, что коэффициенты переменной в полиноме P ( y , x ) - это в точности полиномы S n k ( x ) . Но нам нужны гауссы (и так - вычитания), чтобы извлечь эти коэффициенты из n + 1 значений P ( y ) в n + 1 различных точках. Мой вопрос касается не имеет ли «монотонное слово» нет Гаусса действительно , в этом случае. (С угаданным ответом - НЕТ.) Я не уверен, что для этого достаточно избавиться от сроков >yP(y,x)Skn(x)n+1P(y)n+1>kk