Monoton arithmetische Schaltungskomplexität von elementaren symmetrischen Polynomen?

Die $k$ - te elementare symmetrische Polynom $S_k^n(x_1,\ldots,x_n)$ ist die Summe aller Produkte von unterschiedlichen Variablen. Ich interessiere mich für die monotone arithmetische Schaltungskomplexität dieses Polynoms. Ein einfacher dynamischer Programmieralgorithmus (wie auch in Abb. 1 unten) ergibt eine Schaltung mit Gattern. $\binom{n}{k}$ $k$ $(+,\times)$ $(+,\times)$ $O(kn)$

Frage: Ist eine Untergrenze von bekannt? $\Omega(kn)$

Eine -Schaltung ist schief, wenn mindestens einer der beiden Eingänge jedes Produkttors eine Variable ist. Eine solche Schaltung ist eigentlich die gleiche wie ein Schalt- und Gleichrichtungsnetzwerk (ein gerichteter azyklischer Graph mit einigen durch Variablen gekennzeichneten Kanten; jeder st-Pfad gibt das Produkt seiner Bezeichnungen an, und die Ausgabe ist die Summe über alle st-Pfade). Markov erwies sich bereits vor 40 Jahren als überraschend knapp: Eine minimale monotone Arithmetik-Skew-Schaltung für hat genau Produkt-Gates. Die obere Schranke ergibt sich aus Abb. 1: $(+,\times)$ $S_k^n$ $k(n-k+1)$

Aber ich habe keinen Versuch gesehen, eine solche Untergrenze für nicht schiefe Schaltungen zu beweisen. Ist das nur unsere "Arroganz", oder gibt es auf dem Weg einige inhärente Schwierigkeiten?

PS Ich weiß, dass Tore notwendig sind, um alle gleichzeitig zu berechnen . Dies folgt aus der unteren Grenze der Größe von monotonen Booleschen Schaltkreisen, die den 0-1-Eingang sortieren; siehe Seite 158 des Buches von Ingo Wegener . Das AKS-Sortiernetzwerk impliziert auch, dass in diesem (booleschen) Fall Gatter ausreichen. Tatsächlich haben Baur und Strassen eine enge Grenze für die Größe einer nicht monotonen Rechenschaltung für bewiesen . Aber was ist mit monotonen Rechenschaltungen? $\Omega(n\log n)$ $S_1^n,\ldots,S_n^n$ $O(n\log n)$ $\Theta(n\log n)$ $S_{n/2}^n$

cc.complexity-theory circuit-complexity lower-bounds arithmetic-circuits dynamic-programming Stasys
quelle

Eine Herausforderung besteht darin, dass wir wissen , wie man solche Dinge effizient berechnet , wenn Sie die "monotone" Einschränkung entfernen . Sie können den Wert aller (alle elementaren symmetrischen Polynome auswerten ) in mithilfe der FFT-basierten Polynommultiplikation berechnen. Der Nachweis einer unteren Grenze von im monotonen Schaltungsmodell würde den Nachweis von erfordern. $S_0^n,\dots,S_n^n$ $n+1$ $O(n \log^2 n)$ $\Omega(nk)$ $\Omega(n^2)$ untere Grenze der Polynommultiplikation.

Hier ist wie. Führen Sie ein formal unbekanntes und betrachten Sie das Polynom $y$

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

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

Man beachte, dass dies ein univariates Polynom mit unbekanntem und mit Grad ist , da die bekannte Konstanten sind . Nun können Sie feststellen, dass der Koeffizient von in genau ist. Um also alle auszuwerten , reicht es aus, zu berechnen . $x_i$ $y$ $n$ $y^k$ $P(y)$ $S_k^n$ $S_0^n,\dots,S_n^n$ $P(y)$

Dies ermöglicht es, in Zeit zu berechnen : Bilden Sie einen ausgeglichenen binären Baum von Polynomen mit den an den Blättern und multiplizieren Sie die Polynome. Die Multiplikation von zwei Polynomen des Grades benötigt mit FFT-Techniken die Zeit , sodass wir die Wiederholung $P(y)$ $O(n \lg^2 n)$ $(1+x_i y)$ $d$ $O(d \lg d)$ -Faktoren. , was sich zu löst. Der ignoriere ich $T(n) = 2 T(n/2) + O(n \lg n)$ $T(n) = O(n \lg^2 n)$ $\text{poly}(\lg \lg n)$

Wenn Sie sich für den Fall interessieren, dass sehr klein ist, können Sie in mit ähnlichen Tricks berechnen , wobei Sie berücksichtigen, dass Sie sich nur für interessieren (dh alle Terme von oder höheren Potenzen von wegwerfen ). $k$ $S_0^n,\dots,S_k^n$ $O(n \lg^2 k)$ $P(x) \bmod y^{k+1}$ $y^{k+1}$ $y$

Natürlich verwendet die FFT die Subtraktion, so dass sie naiv nicht in einer monotonen Schaltung ausgedrückt werden kann. Ich weiß nicht, ob es eine andere Möglichkeit gibt, Polynome effizient mit monotonen Arithmetikschaltungen zu multiplizieren, aber jede effiziente monotone Methode zur Polynommultiplikation führt sofort zu einem Algorithmus für Ihr Problem. Untere Schranken für Ihr Problem erfordern / implizieren also untere Schranken für die Polynommultiplikation.

DW
quelle

DW, danke, dass du dich an diese Konstruktion erinnert hast! Es wird normalerweise Ben-Or zugeschrieben, und ich hätte es erwähnen sollen. Die Konstruktion ergibt auch eine <i> Formel </ i> mit der Größe

und der Tiefe nur

(!), Die den Operator

berechnet (durch Auswertung von

bei einigen

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$ Punkte). Dies wurde verwendet, um homogene und inhomogene Formeln mit geringer Tiefe zu trennen. Wie Sie bereits erwähnt haben, wird bei der Konstruktion im Wesentlichen Subtraktion verwendet. Meine Frage lautet also: Wie "substanziell" ist diese Verwendung tatsächlich? Dies könnte auch in Szenarien mit eingeschränkter Tiefe interessant sein.

Stasys

@Stasys: Ich denke, Subtraktion ist ziemlich wichtig. Nämlich. die Nisan-Wigderson-Untergrenze für homogene Kreisläufe der Tiefe 3 ; In homogenen Tiefen-3-Kreisen ist es sinnlos, Terme zu berechnen, deren Grad vom Grad der Ausgabe abweicht. Dies begrenzt also die Arten von Stornierungen, die auftreten können. Während in der Ben-Or-Konstruktion zum Berechnen von

ein Polynom des Grades

berechnet werden muss (obwohl die Ausgabe den Grad

), und dann wird die Löschung entscheidend verwendet, um die Terme der Grade

. Dies ist kein Beweis, nur eine Intuition ...

S_{k}^{n}

$S_k^n$

n

$n$

k < n

$k < n$

> k

$> k$

Joshua Grochow

@Joshua: Ja, wir wissen, dass die Koeffizienten der Variablen

im Polynom

genau die Polynome

. Aber wir brauchen Gauß (und so - Subtraktionen), um diese Koeffizienten aus

Werten von

verschiedenen Punkten zu extrahieren . Meine Frage lautet, ob das "monotone Wort" in diesem Fall tatsächlich kein Gauß hat . (Mit einer erratenen Antwort - NEIN.) Ich bin mir nicht sicher, ob es dazu ausreicht, die Gradangaben

loszuwerden

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$

> k

$> k$

k

$k$

Monoton arithmetische Schaltungskomplexität von elementaren symmetrischen Polynomen?

Antworten: