Avaliando polinômios simétricos

Seja um polinômio simétrico , ou seja, um polinômio tal que para todo e todas as permutações . Por conveniência, podemos assumir que é um campo finito, para evitar problemas com o modelo de computação.$f:\mathbb{K}^n \to \mathbb{K}$x ∈ K n σ ∈ S n $f(x)=f(\sigma(x))$$x \in \mathbb{K}^n$$\sigma \in S_n$$\mathbb{K}$

Vamos denotar a complexidade da computação , ou seja, a complexidade de um algoritmo que, dado , retorna . Podemos de alguma forma caracterizar , com base nas propriedades de ? Por exemplo, garantimos que é polinomial (em ) para todos os polinômios simétricos ?f x f ( x ) C ( f ) f C ( f ) n $C(f)$$f$$x$$f(x)$$C(f)$$f$$C(f)$$n$$f$

Como caso especial, parece que (a) podemos calcular os polinômios da soma de potência em tempo e (b) podemos calcular os polinômios simétricos elementares em tempo , usando as identidades de Newton . Como conseqüência, se é uma soma ponderada de monômios em que nenhuma variável é aumentada para uma potência maior que 1 (ou seja, se é multilinear), então pode ser calculado em tempo polinomial (já que pode ser expresso como uma soma ponderada polinômios simétricos elementares). Por exemplo, quando$\text{poly}(n)$$\text{poly}(n)$f f K = G F ( 2 $f$$f$$f$$\mathbb{K}=GF(2)$, todos os polinômios simétricos podem ser calculados em tempo polinomial. Alguém pode dizer algo mais do que isso?

A questão parece bastante aberta. Ou talvez você queira ter uma caracterização precisa da complexidade de tempo de qualquer polinômio simétrico possível sobre campos finitos?

De qualquer forma, pelo menos ao meu conhecimento, existem vários resultados bem conhecidos sobre a complexidade temporal dos polinômios simétricos de computação:

1. Se é um polinômio simétrico elementar sobre um campo finito, ele pode ser calculado por circuitos T C 0 uniformes de tamanho polinomial .$f$$TC^0$

2. Se é um polinômio simétrico elementar sobre um campo característico 0 , então ele pode ser calculado pela profundidade do tamanho do polinômio, três circuitos algébricos uniformes (como você já mencionou o polinômio de Newton; ou pela fórmula de interpolação de Lagrange); então acredito que isso se traduz em circuitos booleanos uniformes de tamanho polinomial (embora talvez não de profundidade constante) (mas isso pode depender do campo específico em que você está trabalhando; por simplicidade, você pode considerar o anel de números inteiros; números inteiros, presumo que T C 0 seja suficiente para calcular polinômios simétricos em qualquer caso.)$f$$0$$TC^0$

3. Se é um polinômio simétrico sobre um campo finito, existe um limite inferior exponencial na profundidade de três circuitos algébricos para f (por Grigoriev e Razborov (2000) [seguindo Grigoriev e Karpinsky 1998]). Mas, como mencionado em 1 acima, isso corresponde apenas aos limites inferiores do circuito booleano de profundidade constante (enquanto existem pequenos circuitos booleanos uniformes em T C 0 ; significando também que os polinômios são computáveis ​​em tempo polinomial). $f$$f$$TC^0$

Provavelmente existem resultados mais conhecidos sobre a complexidade temporal de polinômios simétricos ...