Mengevaluasi polinomial simetris

Misalkan menjadi polinomial simetris , yaitu polinomial sehingga untuk semua dan semua permutasi . Untuk kenyamanan, kita dapat menganggap adalah bidang yang terbatas, untuk menghindari mengatasi masalah dengan model perhitungan.$f:\mathbb{K}^n \to \mathbb{K}$$f(x)=f(\sigma(x))$$x \in \mathbb{K}^n$$\sigma \in S_n$$\mathbb{K}$

Misalkan menunjukkan kompleksitas komputasi$C(f)$ , yaitu kompleksitas algoritma yang, diberikan x , mengembalikan f ( x ) . Bisakah kita entah bagaimana mengkarakterisasi C ( f ) , berdasarkan pada properti dari f ? Misalnya, apakah kami dijamin bahwa C ( f ) adalah polinomial (dalam n ) untuk semua polinomial simetris f ?$f$$x$$f(x)$$C(f)$$f$$C(f)$$n$$f$

Sebagai kasus khusus, sepertinya (a) kita dapat menghitung jumlah daya polinomial dalam waktu , dan (b) kita dapat menghitung polinomial simetris elementer dalam waktu poli ( n ) , menggunakan identitas Newton . Sebagai konsekuensinya, jika f adalah jumlah tertimbang dari monomial di mana tidak ada variabel yang dinaikkan ke daya yang lebih tinggi dari 1 (yaitu, jika f adalah multilinear), maka f dapat dihitung dalam waktu polinomial (karena dapat dinyatakan sebagai jumlah tertimbang polinomial simetris dasar). Misalnya, ketika$\text{poly}(n)$$\text{poly}(n)$$f$$f$$f$$\mathbb{K}=GF(2)$, maka setiap polinomial simetris dapat dihitung dalam waktu polinomial. Bisakah seseorang mengatakan lebih dari ini?

Pertanyaannya sepertinya cukup terbuka berakhir. Atau mungkin Anda ingin memiliki karakterisasi yang tepat dari kompleksitas waktu dari setiap polinomial simetris yang mungkin lebih dari bidang terbatas?

Bagaimanapun, setidak-tidaknya setahu saya, ada beberapa hasil terkenal tentang kompleksitas waktu komputasi polinomial simetris:

1. Jika adalah polinomial simetris dasar atas lapangan terbatas maka dapat dihitung dengan polinomial-ukuran seragam T C 0 sirkuit.$f$$TC^0$

2. Jika adalah polinomial simetris elementer pada bidang karakteristik 0 , maka f dapat dihitung dengan kedalaman polinomial ukuran tiga sirkuit aljabar seragam (seperti yang telah Anda sebutkan polinomial Newton; atau dengan rumus interpolasi Lagrange); dan jadi saya percaya ini kemudian diterjemahkan ke sirkuit Boolean seragam ukuran-polinomial (meskipun mungkin tidak dengan kedalaman konstan) (tapi ini mungkin tergantung pada bidang spesifik tempat Anda bekerja; untuk kesederhanaan Anda dapat mempertimbangkan cincin bilangan bulat; meskipun untuk bilangan bulat aku nyana T C 0 cukup untuk menghitung polinomial simetris dalam hal apapun.)$f$$0$$TC^0$

3. Jika adalah polinomial simetris di atas bidang hingga maka ada batas bawah eksponensial pada kedalaman tiga aljabar sirkuit untuk f (oleh Grigoriev dan Razborov (2000) [mengikuti Grigoriev dan Karpinsky 1998]). Tapi, sebagaimana disebutkan dalam 1 di atas, berkorespondensi ini hanya untuk konstan mendalam Boolean sirkuit batas bawah (sementara ada seragam kecil sirkuit Boolean di T C 0 ; berarti juga bahwa polinomial yang dihitung dalam waktu polinomial). $f$$f$$TC^0$

Mungkin ada hasil yang lebih diketahui tentang kompleksitas waktu polinomial simetris ...