Monotoniczna złożoność obwodu arytmetycznego elementarnych wielomianów symetrycznych?

W $k$ -tej elementarne wielomian symetryczny $S_k^n(x_1,\ldots,x_n)$ jest sumą wszystkich produktów różnych zmiennych. Interesuje mnie złożoność obwodu arytmetycznego monotonicznego tego wielomianu. Prosty algorytm programowania dynamicznego (jak również ryc. 1 poniżej) daje obwód z bramkami . $\binom{n}{k}$ $k$ $(+,\times)$ $(+,\times)$ $O(kn)$

Pytanie: Czy znana jest dolna granica ? $\Omega(kn)$

obwód jest skośna , jeżeli co najmniej jeden z dwóch wejść każdego bramy produkt jest zmienny. Taki obwód jest w rzeczywistości taki sam jak sieć przełączająco-prostownicza (ukierunkowany wykres acykliczny z niektórymi krawędziami oznaczonymi zmiennymi; każda ścieżka st daje iloczyn swoich etykiet, a wynik jest sumą wszystkich ścieżek st). Już 40 lat temu Markow udowodnił zaskakująco ścisły wynik: minimalny monotoniczny arytmetyczny obwód skośny dla ma dokładnie bramek produktu. Górna granica wynika z fig. 1: $(+,\times)$ $S_k^n$ $k(n-k+1)$

Ale nie widziałem żadnej próby udowodnienia takiej dolnej granicy dla obwodów bez skosu. Czy to tylko nasza „arogancja”, czy też po drodze pojawiają się jakieś nieodłączne trudności?

PS Wiem, że bramki są niezbędne do jednoczesnego obliczenia wszystkich . Wynika to z dolnej granicy wielkości monotonicznych obwodów boolowskich sortujących wejście 0-1; patrz strona 158 książki Ingo Wegenera . Sieć sortowania AKS sugeruje również, że w tym przypadku (boolowskim) wystarczające są bramki . W rzeczywistości Baur i Strassen udowodnili ścisłe powiązanie wielkości niemonotonicznego obwodu arytmetycznego dla . Ale co z monotonicznymi obwodami arytmetycznymi? $\Omega(n\log n)$ $S_1^n,\ldots,S_n^n$ $O(n\log n)$ $\Theta(n\log n)$ $S_{n/2}^n$

— Stasys
źródło

Jednym z wyzwań jest to, że jeśli usunąć „monotonia” ograniczenie, że nie wiem jak obliczyć takie rzeczy sprawnie. Można obliczyć wartość wszystkich (oszacować wszystkie elementarne wielomiany symetryczne) w $S_0^n,\dots,S_n^n$ $n+1$ , używając mnożenia wielomianowego opartego na FFT. Tak więc udowodnieniedolnej granicy w modelu obwodu monotonicznego wymagałoby udowodnienia $O(n \log^2 n)$ $\Omega(nk)$ $\Omega(n^2)$ dolna granica mnożenia wielomianowego.

Oto jak. Wprowadź formalną nieznaną i rozważ wielomian $y$

P (y) = \prod_{i = 1}^{n} (1 + x_{i} y) .

$P(y) = \prod_{i=1}^n (1 + x_i y).$

Warto zauważyć, że „y Znane są stałe, to jest w jednowymiarowej wielomianu o nieznanej i stopnia . Teraz możesz zauważyć, że współczynnik w wynosi dokładnie , więc aby ocenić wszystkie , wystarczy obliczyć . $x_i$ $y$ $n$ $y^k$ $P(y)$ $S_k^n$ $S_0^n,\dots,S_n^n$ $P(y)$

To sprawia, że możliwe jest obliczanie w Czas budowy zrównoważonej binarne drzewo wielomianów z „S w liściach i mnożą wielomiany. Pomnożenie dwóch wielomianów stopnia zajmuje czas przy użyciu technik FFT, więc otrzymujemy nawrót $P(y)$ $O(n \lg^2 n)$ $(1+x_i y)$ $d$ $O(d \lg d)$ , co rozwiązuje się do . Dla wygody czynniki . $T(n) = 2 T(n/2) + O(n \lg n)$ $T(n) = O(n \lg^2 n)$ $\text{poly}(\lg \lg n)$

Jeśli zależy ci na przypadku, w którym jest bardzo małe, możesz obliczyć w czasie przy użyciu podobnych sztuczek, pamiętając, że dbasz tylko o $k$ $S_0^n,\dots,S_k^n$ $O(n \lg^2 k)$ (tj. wyrzucenie wszystkich składników lub wyższych mocy). $P(x) \bmod y^{k+1}$ $y^{k+1}$ $y$

Oczywiście FFT używa odejmowania, więc naiwnie nie można tego wyrazić w obwodzie monotonicznym. Nie wiem, czy istnieje jakiś inny sposób wydajnego zwielokrotnienia wielomianów za pomocą monotonicznych obwodów arytmetycznych, ale każda skuteczna metoda monotoniczna do mnożenia wielomianowego natychmiast prowadzi do algorytmu dla twojego problemu. Tak więc dolne granice twojego problemu wymagają / implikują dolne granice mnożenia wielomianowego.

— DW
źródło

DW, dziękuję za odwołanie tej konstrukcji! Jest to zwykle przypisywane Ben-Orowi i powinienem o tym wspomnieć. Konstrukcja daje również <i> wzór </i> o rozmiarze

i tylko głębokości

(!), Obliczając operator

(przez oszacowanie

przy pewnym

O (n^{2})

$O(n^2)$

3

$3$

S_{0}^{n}, \dots, S_{n}^{n}

$S_0^n,\ldots,S_n^n$

P (y)

$P(y)$

n + 1

$n+1$ zwrotnica). Służyło to do oddzielania jednorodnych i niejednorodnych formuł o małej głębokości. Ale, jak wspomniałeś, konstrukcja zasadniczo wykorzystuje odejmowanie. Zatem moje pytanie brzmi: jak „znaczące” jest to wykorzystanie? Może to być interesujące również w scenariuszu o ograniczonej głębokości.

— Stasys,

@Stasys: Myślę, że odejmowanie jest bardzo ważne. Mianowicie. dolna granica Nisana-Wigdersona na jednorodnych obwodach głębokości 3 ; w jednorodnych obwodach o głębokości 3 chodzi o to, że nie ma sensu obliczać warunków, których stopnie różnią się od stopnia mocy wyjściowej. To ogranicza rodzaje anulowań, które mogą się zdarzyć. Podczas gdy w konstrukcji Ben-Or, aby obliczyć

, należy obliczyć wielomian stopnia

(nawet jeśli wynik ma stopień

), a następnie należy użyć anulowania, aby pozbyć się warunków stopni

. To nie jest dowód, tylko intuicja ...

S_{k}^{n}

$S_k^n$

n

$n$

k < n

$k < n$

> k

$> k$

— Joshua Grochow

@Joshua: tak, wiemy, że współczynniki zmiennej

w wielomianu

są dokładnie wielomianami

. Ale potrzebujemy Gaussa (i tak - odejmowania), aby wyodrębnić te współczynniki z wartości

wartości

różnych punktach. Moje pytanie dotyczy tego, czy w tym przypadku „monotonne słowo” rzeczywiście nie ma Gaussa . (Przy odgadłej odpowiedzi - NIE.) Nie jestem pewien, czy do tego wystarczy pozbyć się stopni

y

$y$

P (y, x)

$P(y,x)$

S_{k}^{n} (x)

$S_k^n(x)$

n + 1

$n+1$

P (y)

$P(y)$

n + 1

$n+1$

. Musimyznaleźćte

pierwszych współczynników.

> k

$> k$

k

$k$

— Stasys,