Évaluation des polynômes symétriques

Soit un polynôme symétrique , c'est-à-dire un polynôme tel que pour tous les et toutes les permutations . Pour plus de commodité, nous pouvons supposer que est un champ fini, pour éviter de résoudre les problèmes avec le modèle de calcul. f ( x ) = f ( σ ( x ) ) x ∈ K n σ ∈ S n $f:\mathbb{K}^n \to \mathbb{K}$$f(x)=f(\sigma(x))$$x \in \mathbb{K}^n$$\sigma \in S_n$$\mathbb{K}$

Soit la complexité du calcul de , c'est-à-dire la complexité d'un algorithme qui, étant donné , renvoie . Pouvons-nous caractériser en quelque sorte , sur la base des propriétés de ? Par exemple, avons-nous la garantie que est polynomial (en ) pour tous les polynômes symétriques ?f x f ( x ) C ( f ) f C ( f ) n $C(f)$$f$$x$$f(x)$$C(f)$$f$$C(f)$$n$$f$

Dans un cas particulier, il semble que (a) nous pouvons calculer les polynômes de somme de puissance dans le temps , et (b) nous pouvons calculer les polynômes symétriques élémentaires dans le temps , en utilisant les identités de Newton . Par conséquent, si est une somme pondérée de monômes où aucune variable n'est élevée à une puissance supérieure à 1 (c'est-à-dire si est multilinéaire), alors peut être calculé en temps polynomial (car il peut être exprimé comme une somme pondérée de polynômes symétriques élémentaires). Par exemple, lorsque$\text{poly}(n)$$\text{poly}(n)$f f K = G F ( 2 $f$$f$$f$$\mathbb{K}=GF(2)$, alors chaque polynôme symétrique peut être calculé en temps polynomial. Peut-on dire autre chose que cela?

La question semble assez ouverte. Ou peut-être souhaitez-vous avoir une caractérisation précise de la complexité temporelle de tout polynôme symétrique possible sur des champs finis?

En tout cas, du moins à ma connaissance, il existe plusieurs résultats bien connus sur la complexité temporelle du calcul de polynômes symétriques:

1. Si est un polynôme symétrique élémentaire sur un champ fini, il peut être calculé par des circuits uniformes de taille polynomiale .T C $f$$TC^0$

2. Si est un polynôme symétrique élémentaire sur un champ caractéristique , alors il peut être calculé par la profondeur de taille polynomiale de trois circuits algébriques uniformes (comme vous l'avez déjà mentionné le polynôme de Newton; ou par la formule d'interpolation de Lagrange); et donc je crois que cela se traduit alors par des circuits booléens uniformes de taille polynomiale (bien que peut-être pas de profondeur constante) (mais cela peut dépendre du domaine spécifique dans lequel vous travaillez; pour plus de simplicité, vous pourriez considérer l'anneau d'entiers; bien que pour le des entiers, je suppose que est suffisant pour calculer des polynômes symétriques dans tous les cas.)0 T C $f$$0$$TC^0$

3. Si est un polynôme symétrique sur un champ fini, il existe alors une borne inférieure exponentielle sur la profondeur de trois circuits algébriques pour (par Grigoriev et Razborov (2000) [suivant Grigoriev et Karpinsky 1998]). Mais, comme mentionné au point 1 ci-dessus, cela ne correspond qu'aux bornes inférieures du circuit booléen de profondeur constante (alors qu'il existe de petits circuits booléens uniformes dans ; ce qui signifie également que les polynômes sont calculables en temps polynomial). f T C $f$$f$$TC^0$

Il existe probablement des résultats plus connus sur la complexité temporelle du polynôme symétrique ...