Complexité du circuit arithmétique monotone des polynômes symétriques élémentaires?

Le $k$ -ième polynôme symétrique élémentaire est la somme de tous produits de variables distinctes. Je m'intéresse à la complexité du circuit arithmétique monotone de ce polynôme. Un algorithme de programmation dynamique simple (ainsi que la figure 1 ci-dessous) donne un circuit avec des portes .$S_k^n(x_1,\ldots,x_n)$$\binom{n}{k}$$k$$(+,\times)$$(+,\times)$$O(kn)$

Question: une limite inférieure de connue? $\Omega(kn)$

Un circuit est asymétrique si au moins une des deux entrées de chaque porte de produit est une variable. Un tel circuit est en fait le même que le réseau de commutation et de rectification (un graphique acyclique dirigé avec quelques bords étiquetés par des variables; chaque chemin st donne le produit de ses étiquettes, et la sortie est la somme de tous les chemins st). Il y a déjà 40 ans, Markov a prouvé un résultat étonnamment serré: un circuit arithmétique monotone minimal pour a exactement portes de produit. La limite supérieure découle de la figure 1: $(+,\times)$$S_k^n$ $k(n-k+1)$

Mais je n'ai vu aucune tentative de prouver une telle limite inférieure pour les circuits non asymétriques. Est-ce simplement notre «arrogance», ou y a-t-il des difficultés inhérentes observées en cours de route?

PS Je sais que les portes sont nécessaires pour calculer simultanément tous les . Cela découle de la limite inférieure de la taille des circuits booléens monotones triant l'entrée 0-1; voir page 158 du livre d' Ingo Wegener . Le réseau de tri AKS implique également que les portes sont suffisantes dans ce cas (booléen). En fait, Baur et Strassen ont prouvé une limite étroite sur la taille du circuit arithmétique non monotone pour . Mais qu'en est-il des circuits arithmétiques monotones ?S n 1 , … , S n n O ( n log n ) Θ ( n log n ) S n n /$\Omega(n\log n)$$S_1^n,\ldots,S_n^n$$O(n\log n)$$\Theta(n\log n)$$S_{n/2}^n$

Un défi est que si vous supprimez la restriction « monotone », nous ne savons comment calculer ces choses efficacement. Vous pouvez calculer la valeur de tous les (évaluer tous les n + 1 polynômes symétriques élémentaires) en temps O ( n log 2 n ) , en utilisant la multiplication polynomiale basée sur FFT. Donc, prouver une borne inférieure Ω ( n k ) dans le modèle de circuit monotone nécessiterait de prouver un Ω ( n 2$S_0^n,\dots,S_n^n$$n+1$$O(n \log^2 n)$$\Omega(nk)$$\Omega(n^2)$ borne inférieure sur la multiplication polynomiale.

Voici comment. Introduire un inconnu formel , et considérer le polynôme$y$

Notez que les étant des constantes connues, il s'agit d'un polynôme univarié avec y inconnu et de degré n . Vous pouvez maintenant noter que le coefficient de y k dans P ( y ) est exactement S n k , donc pour évaluer tous les S n 0 , … , S n n , il suffit de calculer P ( y ) .$x_i$$y$$n$$y^k$$P(y)$$S_k^n$$S_0^n,\dots,S_n^n$$P(y)$

Cela permet de calculer en temps O ( n lg 2 n ) : construire un arbre binaire équilibré de polynômes avec les ( 1 + x i y ) à la feuille, et multiplier les polynômes. La multiplication de deux polynômes de degré d prend du temps O ( d lg d ) en utilisant des techniques FFT, donc on obtient la récurrence T ( n ) = 2 T ( n / 2 ) $P(y)$$O(n \lg^2 n)$$(1+x_i y)$$d$$O(d \lg d)$ , qui résout à T ( n ) = O ( n lg 2 n ) . Pour plus de commodité, j'ignore les facteurs poly ( lg lg n ) .$T(n) = 2 T(n/2) + O(n \lg n)$$T(n) = O(n \lg^2 n)$$\text{poly}(\lg \lg n)$

Si vous vous souciez du cas où est très petit, vous pouvez calculer S n 0 , … , S n k en temps O ( n lg 2 k ) en utilisant des astuces similaires, en gardant à l'esprit que vous ne vous souciez que du mod P ( x ) y k + 1 (c.-à-d. jeter tous les termes de y k + 1 ou des puissances supérieures de y ).$k$$S_0^n,\dots,S_k^n$$O(n \lg^2 k)$$P(x) \bmod y^{k+1}$$y^{k+1}$$y$

Bien sûr, la FFT utilise la soustraction, donc naïvement elle n'est pas exprimable dans un circuit monotone. Je ne sais pas s'il existe un autre moyen de multiplier efficacement les polynômes avec des circuits arithmétiques monotones, mais toute méthode monotone efficace pour la multiplication polynomiale conduit immédiatement à un algorithme pour votre problème également. Ainsi, les limites inférieures de votre problème nécessitent / impliquent des limites inférieures pour la multiplication polynomiale.