Complejidad del circuito aritmético monótono de polinomios simétricos elementales?

El $k$ -ésimo polinomio simétrico elemental $S_k^n(x_1,\ldots,x_n)$ es la suma de todos los productos de distintas variables. Estoy interesado en la complejidad del circuito aritmético monótono de este polinomio. Un algoritmo de programación dinámica simple (así como la Fig. 1 a continuación) proporciona un circuito con compuertas .$\binom{n}{k}$$k$$(+,\times)$$(+,\times)$$O(kn)$

Pregunta: ¿Se conoce un límite inferior de ? $\Omega(kn)$

Un circuito está sesgado si al menos una de las dos entradas de cada puerta de producto es una variable. Tal circuito es en realidad lo mismo que la red de conmutación y rectificación (un gráfico acíclico dirigido con algunos bordes etiquetados por variables; cada ruta st proporciona el producto de sus etiquetas, y la salida es la suma de todas las rutas st). Hace ya 40 años, Markov demostró un resultado sorprendentemente ajustado: un circuito de inclinación aritmética monótono mínimo para tiene exactamente puertas de producto. El límite superior se deduce de la Fig. 1: $(+,\times)$$S_k^n$ $k(n-k+1)$

Pero no he visto ningún intento de probar un límite tan bajo para circuitos no sesgados. ¿Es esta simplemente nuestra "arrogancia", o hay algunas dificultades inherentes observadas en el camino?

PD: Sé que las compuertas son necesarias para calcular simultáneamente todos los . Esto se deduce del límite inferior del tamaño de los circuitos booleanos monótonos que ordenan la entrada 0-1; ver página 158 del libro de Ingo Wegener . La red de clasificación AKS también implica que las compuertas son suficientes en este caso (booleano). En realidad, Baur y Strassen han demostrado ser un estricto en el tamaño del circuito aritmético no monótono para . Pero, ¿qué pasa con los circuitos aritméticos monótonos ?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$

Uno de los retos es que si se quita la restricción "monótona", que sí sabemos cómo calcular estas cosas de manera eficiente. Puede calcular el valor de todos los (evaluar todos los polinomios simétricos elementales n + 1 ) en el tiempo O ( n log 2 n ) , utilizando la multiplicación polinómica basada en FFT. Por lo tanto, probar un límite inferior de Ω ( n k ) en el modelo de circuito monótono requeriría probar un Ω ( n 2$S_0^n,\dots,S_n^n$$n+1$$O(n \log^2 n)$$\Omega(nk)$$\Omega(n^2)$ límite inferior en la multiplicación polinómica.

Así es cómo. Introduzca una desconocida formal y considere el polinomio$y$

Tenga en cuenta que dado que las son constantes conocidas, este es un polinomio univariado con y desconocido y con grado n . Ahora puede observar que el coeficiente de y k en P ( y ) es exactamente S n k , así que para evaluar todos los S n 0 , ... , S $x_i$$y$$n$$y^k$$P(y)$$S_k^n$ , es suficiente calcularP(y).$S_0^n,\dots,S_n^n$$P(y)$

Esto hace posible calcular en el tiempo O ( n lg 2 n ) : construya un árbol binario equilibrado de polinomios con los ( 1 + x i y ) en las hojas y multiplique los polinomios. Multiplicar dos polinomios de grado d lleva tiempo O ( d lg d ) utilizando técnicas FFT, por lo que obtenemos la recurrencia T ( n ) = 2 T ( n / 2 ) $P(y)$$O(n \lg^2 n)$$(1+x_i y)$$d$$O(d \lg d)$ , que se resuelve en T ( n ) = O ( n lg 2 n ) . Por conveniencia, estoy ignorando losfactores poli ( 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 te importa el caso donde es muy pequeño, puedes calcular S n 0 , ... , S n k en tiempo O ( n lg 2 k ) usando trucos similares, teniendo en cuenta que solo te importa el mod P ( x ) y k + $k$$S_0^n,\dots,S_k^n$$O(n \lg^2 k)$$P(x) \bmod y^{k+1}$ (es decir, descartar todos los términos de o potencias superiores de y ).$y^{k+1}$$y$

Por supuesto, el FFT usa sustracción, por lo que ingenuamente no se puede expresar en un circuito monótono. No sé si hay alguna otra manera de multiplicar polinomios de manera eficiente con circuitos aritméticos monótonos, pero cualquier método monótono eficiente para la multiplicación polinomial también conduce inmediatamente a un algoritmo para su problema. Entonces, los límites inferiores de su problema requieren / implican límites inferiores para la multiplicación polinómica.