В -й элементарный симметричный полином является суммой всех продуктов различных переменных. Меня интересует сложность монотонной арифметической схемы этого многочлена. Простой алгоритм динамического программирования (как и рис. 1 ниже) дает схему с воротами .
Вопрос: Известна ли нижняя граница ?
цепи перекос , если по крайней мере один из двух входов каждого затвора продукта является переменной. Такая схема на самом деле такая же, как сеть с коммутацией и выпрямлением (ориентированный ациклический граф с некоторыми ребрами, помеченными переменными; каждый st-путь дает произведение своих меток, а результат представляет собой сумму по всем st-путям). Уже 40 лет назад Марков доказал удивительно жесткий результат: минимальная монотонная арифметическая схема для имеет ровно . Верхняя оценка следует из фиг.1.:
Но я не видел ни одной попытки доказать такую нижнюю оценку для нескошенных цепей. Это только наше «высокомерие», или есть какие-то присущие трудности, встречающиеся на этом пути?
PS Я знаю, что ворота необходимы для одновременного вычисления всех . Это следует из нижней границы размера монотонных логических схем, сортирующих вход 0-1; см. стр. 158 книги Инго Вегенера . АКС сортировка сети также подразумевает , что ворота достаточно в этом (логическое) случае. На самом деле Баур и Штрассен доказали тесную связь с размером немонотонной арифметической схемы для . Но как насчет монотонных арифметических схем?S n 1 , … , S n n O ( n log n ) Θ ( n log n ) S n n / 2