Evaluación de polinomios simétricos

10

Sea un polinomio simétrico , es decir, un polinomio tal que f ( x ) = f ( σ ( x ) ) para todas las x K n y todas las permutaciones σ S n . Por conveniencia, podemos suponer que K es un campo finito, para evitar abordar problemas con el modelo de computación.F:KnorteKF(X)=F(σ(X))XKnorteσSnorteK

Supongamos que denota la complejidad de calcular f , es decir, la complejidad de un algoritmo que, dado x , devuelve f ( x ) . ¿Podemos de alguna manera caracterizar C ( f ) , en base a las propiedades de f ? Por ejemplo, ¿estamos garantizados de que C ( f ) es polinomial (en n ) para todos los polinomios simétricos f ?C(F)FXF(X)C(F)FC(F)norteF

Como caso especial, parece que (a) podemos calcular los polinomios de suma de potencia en el tiempo , y (b) podemos calcular los polinomios simétricos elementales en el tiempo poli ( n ) , utilizando las identidades de Newton . Como consecuencia, si f es una suma ponderada de monomios donde ninguna variable se eleva a una potencia superior a 1 (es decir, si f es multilineal), entonces f puede calcularse en tiempo polinomial (ya que puede expresarse como una suma ponderada de polinomios simétricos elementales). Por ejemplo, cuando K = G F (escuela politécnica(norte)escuela politécnica(norte)FFF , entonces cada polinomio simétrico se puede calcular en tiempo polinómico. ¿Se puede decir algo más que esto?K=solF(2)

DW
fuente
1
Si está interesado en el cálculo sobre es posible que desee aclarar el modelo de cálculo. R
Kaveh
1
@Kaveh, ahh, excelente punto. Supongo que no estoy súper enfocado en ningún campo, así que supongo que preguntaré sobre campos finitos para que ese problema desaparezca. Me interesa más si existen resultados o técnicas sistemáticas para determinar la complejidad de evaluar un polinomio simétrico . F
DW
1
¿Cómo se especifica f? Esto es crucial para la complejidad de la evaluación.
Thomas
2
@ Thomas, no debería importar. Para cualquier fija , C ( f ) está bien definida (es la complejidad del mejor algoritmo para calcular f ). Esto está bien definido y no depende de cómo se "especifica" f . (Tenga en cuenta que f no es una entrada al algoritmo, por lo que no es necesario definir su representación). O, para decirlo de otra manera: si tengo una función simétrica f que quiero calcular, ¿hay alguna técnica o resultado? para ayudarme a encontrar un algoritmo eficiente para calcular f o para determinar qué tan eficientemente se puede calcular mi f ? FC(F)FFFFFF
DW
1
@ Thomas, sí: si hay resultados o técnicas que son aplicables cuando el grado no es demasiado grande, eso suena útil. (Por ejemplo, si el grado wrt de cada variable, considerado por separado, es como máximo una pequeña constante , ¿podemos decir algo? El último párrafo de mi pregunta trata el caso c = 1 ; ¿podemos decir más? O, alternativamente, si el grado total de f no es demasiado grande, ¿podemos decir algo?)CC=1F
DW

Respuestas:

10

La pregunta parece bastante abierta. ¿O tal vez desea tener una caracterización precisa de la complejidad temporal de cualquier posible polinomio simétrico sobre campos finitos?

En cualquier caso, al menos que yo sepa, hay varios resultados bien conocidos sobre la complejidad temporal de la computación de polinomios simétricos:

  1. Si es un polinomio simétrico elemental sobre un campo finito, entonces puede calcularse mediante circuitos T C 0 uniformes de tamaño polinómico .FTC0 0

  2. Si es un polinomio simétrico elemental sobre un campo 0 característico , entonces se puede calcular por profundidad polinómica de tamaño tres circuitos algebraicos uniformes (como ya mencionó el polinomio de Newton; o por la fórmula de interpolación de Lagrange); así que creo que esto se traduce en circuitos booleanos uniformes de tamaño polinómico (aunque quizás no de profundidad constante) (pero esto puede depender del campo específico en el que esté trabajando; por simplicidad, podría considerar el anillo de enteros; aunque para el enteros supongo que T C 0 es suficiente para calcular polinomios simétricos en cualquier caso).F0 0TC0 0

  3. Si es un polinomio simétrico sobre un campo finito, entonces hay un límite inferior exponencial en la profundidad de tres circuitos algebraicos para f (por Grigoriev y Razborov (2000) [siguiendo a Grigoriev y Karpinsky 1998]). Pero, como se mencionó en el punto 1 anterior, esto corresponde solo a los límites inferiores del circuito booleano de profundidad constante (mientras que hay pequeños circuitos booleanos uniformes en T C 0 ; lo que significa también que los polinomios son computables en tiempo polinómico). FFTC0 0

Probablemente hay resultados más conocidos sobre la complejidad temporal del polinomio simétrico ...

Iddo Tzameret
fuente