Ocena wielomianów symetrycznych

Niech będzie symetrycznym wielomianem , tj. Wielomianem takim, że f ( x ) = f ( σ ( x ) ) dla wszystkich x ∈ K n i wszystkich permutacji σ ∈ S n . Dla wygody możemy założyć, że K jest polem skończonym, aby uniknąć rozwiązywania problemów z modelem obliczeniowym.$f:\mathbb{K}^n \to \mathbb{K}$$f(x)=f(\sigma(x))$$x \in \mathbb{K}^n$$\sigma \in S_n$$\mathbb{K}$

Niech oznacza złożoność obliczeń f , tj. Złożoność algorytmu, który przy danym x zwraca f ( x ) . Czy możemy jakoś scharakteryzować C ( f ) na podstawie właściwości f ? Na przykład, czy mamy gwarancję, że C ( f ) jest wielomianem (in n ) dla wszystkich symetrycznych wielomianów f ?$C(f)$$f$$x$$f(x)$$C(f)$$f$$C(f)$$n$$f$

W szczególnym przypadku wygląda to tak: (a) możemy obliczyć wielomian sumy mocy w czasie , i (b) możemy obliczyć elementarne wielomiany symetryczne w czasie poli ( n ) , używając tożsamości Newtona . W konsekwencji, jeżeli f jest ważoną sumą monomialów, w których żadna zmienna nie jest podniesiona do potęgi większej niż 1 (tj. Jeśli f jest wieloliniowa), to f można obliczyć w czasie wielomianowym (ponieważ można go wyrazić jako sumę ważoną elementarnych wielomianów symetrycznych). Na przykład, gdy K = G F $\text{poly}(n)$$\text{poly}(n)$$f$$f$$f$$\mathbb{K}=GF(2)$, wówczas każdy symetryczny wielomian można obliczyć w czasie wielomianowym. Czy można powiedzieć coś więcej niż to?

Pytanie wydaje się dość otwarte. A może chcesz precyzyjnie scharakteryzować złożoność czasową dowolnego możliwego symetrycznego wielomianu nad polami skończonymi?

W każdym razie, przynajmniej według mojej wiedzy, istnieje kilka dobrze znanych wyników dotyczących złożoności czasowej obliczania symetrycznych wielomianów:

1. Jeśli jest elementarnym wielomian symetryczny skończonym pole to może być obliczany za pomocą wielomianu wielkości jednorodna T C 0 obwodów.$f$$TC^0$

2. Jeśli jest elementarnym symetrycznym wielomianem nad charakterystycznym polem 0 , to można go obliczyć na podstawie głębokości wielomianowej o trzech jednolitych obwodach algebraicznych (jak już wspomniałeś wielomian Newtona; lub na podstawie wzoru interpolacji Lagrange'a); i wierzę, że to następnie przekłada się na wielomianowe jednorodne obwody boolowskie (choć być może nie o stałej głębokości) (ale może to zależeć od konkretnego pola, w którym pracujesz; dla uproszczenia możesz rozważyć pierścień liczb całkowitych; chociaż dla Liczby całkowite, jak sądzę, T C 0 wystarczy do obliczenia symetrycznych wielomianów.)$f$$0$$TC^0$

3. Jeśli jest symetrycznym wielomianem nad polem skończonym, wówczas wykładnicza dolna granica na głębokości trzech obwodów algebraicznych dla f (wg Grigoriewa i Razborowa (2000) [według Grigoriewa i Karpinskiego 1998]). Ale, jak wspomniano w 1 powyżej, odpowiada to tylko dolnym granicom obwodu logicznego o stałej głębokości (podczas gdy w T C 0 są małe jednorodne obwody boolowskie ; co oznacza również, że wielomiany można obliczać w czasie wielomianowym). $f$$f$$TC^0$

Prawdopodobnie są bardziej znane wyniki dotyczące złożoności czasowej symetrycznego wielomianu ...