Kompleksitas rangkaian aritmatika monoton polinomial simetris elementer?

Polinomial simetris dasar - adalah jumlah dari semua produk dari variabel yang berbeda. Saya tertarik pada kompleksitas rangkaian aritmatika monoton dari polinomial ini. Algoritma pemrograman dinamis sederhana (serta Gambar 1 di bawah) memberikan sirkuit dengan gerbang . $k$ $S_k^n(x_1,\ldots,x_n)$ $\binom{n}{k}$ $k$ $(+,\times)$ $(+,\times)$ $O(kn)$

Pertanyaan: Apakah batas bawah $\Omega(kn)$ diketahui?

A sirkuit miring jika setidaknya salah satu dari dua input dari setiap gerbang produk adalah variabel. Sirkuit seperti itu sebenarnya sama dengan switching-and-rectifying network (grafik asiklik terarah dengan beberapa sisi dilabeli oleh variabel; setiap jalur st memberikan produk labelnya, dan hasilnya adalah jumlah dari semua jalur st). Sudah 40 tahun yang lalu, Markov terbukti hasil mengejutkan yang ketat: minimal monoton sirkuit condong aritmatika untuk telah persis gerbang produk. Batas atas mengikuti dari Gambar. 1: $(+,\times)$ $S_k^n$ $k(n-k+1)$

Tapi saya belum melihat ada upaya untuk membuktikan batas bawah untuk sirkuit non-condong. Apakah ini hanya "kesombongan" kita, atau adakah beberapa kesulitan yang melekat yang diamati sepanjang jalan?

PS Saya tahu bahwa gerbang $\Omega(n\log n)$ diperlukan untuk secara bersamaan menghitung semua $S_1^n,\ldots,S_n^n$ . Ini mengikuti dari batas bawah pada ukuran sirkuit boolean monoton menyortir input 0-1; lihat halaman 158 buku Ingo Wegener . Jaringan penyortiran AKS juga menyiratkan bahwa gerbang $O(n\log n)$ sudah cukup dalam hal ini (boolean). Sebenarnya, Baur dan Strassen telah membuktikan terikat erat $\Theta(n\log n)$ pada ukuran rangkaian aritmatika non-monoton untuk $S_{n/2}^n$ . Tapi bagaimana dengan sirkuit aritmatika monoton ?

cc.complexity-theory circuit-complexity lower-bounds arithmetic-circuits dynamic-programming Stasys
sumber

Salah satu tantangan adalah bahwa jika Anda menghapus "monoton" pembatasan, kita lakukan tahu bagaimana untuk menghitung hal-hal seperti efisien. Anda dapat menghitung nilai semua (mengevaluasi semua polinomial simetris elementer) dalam waktu , menggunakan penggandaan polinomial berbasis FFT. Jadi, membuktikan batas bawah dalam model rangkaian monoton akan membutuhkan pembuktian $S_0^n,\dots,S_n^n$ $n+1$ $O(n \log^2 n)$ $\Omega(nk)$ $\Omega(n^2)$ batas bawah pada penggandaan polinomial.

Begini caranya. Perkenalkan tidak diketahui secara formal , dan pertimbangkan polinomialnya $y$

P (y) = \prod_{i = 1}^{n} (1 + x_{i} y) .

$P(y) = \prod_{i=1}^n (1 + x_i y).$

Perhatikan bahwa sejak 's adalah konstanta diketahui, ini adalah polinom satu variabel dengan tidak diketahui dan dengan gelar . Sekarang Anda dapat mencatat bahwa koefisien dalam persis , jadi untuk mengevaluasi semua , cukup untuk menghitung . $x_i$ $y$ $n$ $y^k$ $P(y)$ $S_k^n$ $S_0^n,\dots,S_n^n$ $P(y)$

Ini memungkinkan untuk menghitung dalam waktu : membangun pohon biner polinomial seimbang dengan di daun, dan mengalikan polinomialnya. Mengalikan dua polinomial derajat membutuhkan waktu menggunakan teknik FFT, jadi kami mendapatkan rekurensi $P(y)$ $O(n \lg^2 n)$ $(1+x_i y)$ $d$ $O(d \lg d)$ , yang diselesaikan dengan . Untuk kenyamanan, saya mengabaikanfaktor . $T(n) = 2 T(n/2) + O(n \lg n)$ $T(n) = O(n \lg^2 n)$ $\text{poly}(\lg \lg n)$

Jika Anda peduli dengan kasus di mana sangat kecil, Anda dapat menghitung di menggunakan trik yang serupa, mengingat bahwa Anda hanya peduli pada (yaitu, membuang semua istilah atau kekuatan lebih tinggi ). $k$ $S_0^n,\dots,S_k^n$ $O(n \lg^2 k)$ $P(x) \bmod y^{k+1}$ $y^{k+1}$ $y$

Tentu saja, FFT menggunakan pengurangan, jadi secara naif itu tidak bisa diungkapkan dalam rangkaian monoton. Saya tidak tahu apakah ada cara lain untuk melipatgandakan polinomial secara efisien dengan sirkuit aritmatika monoton, tetapi metode monoton yang efisien untuk penggandaan polinomial segera mengarah ke suatu algoritma untuk masalah Anda juga. Jadi, batas bawah pada masalah Anda memerlukan / menyiratkan batas bawah untuk perkalian polinomial.

DW
sumber

DW, terima kasih sudah mengingat konstruksi ini! Ini biasanya dikaitkan dengan Ben-Or, dan saya seharusnya menyebutkannya. Konstruksi juga memberikan formula <i> </i> dengan ukuran

dan kedalaman hanya

(!) Yang menghitung operator

(dengan mengevaluasi

pada beberapa

O (n^{2})

$O(n^2)$

3

$3$

S_{0}^{n}, \dots, S_{n}^{n}

$S_0^n,\ldots,S_n^n$

P (y)

$P(y)$

n + 1

$n+1$ poin). Ini digunakan untuk memisahkan formula kedalaman kecil homogen dan non-homogen. Tetapi, seperti yang Anda sebutkan, konstruksi secara substansial menggunakan pengurangan. Jadi, pertanyaan saya bertanya: seberapa "substansial" penggunaan ini sebenarnya? Ini bisa menarik juga dalam skenario kedalaman terbatas.

Stasys

@Stasys: Saya pikir pengurangan cukup penting. Yaitu. Nisan-Wigderson terikat lebih rendah pada kedalaman 3 sirkuit homogen ; di sirkuit 3 kedalaman homogen, intinya adalah bahwa tidak ada gunanya menghitung istilah yang derajatnya berbeda dari tingkat output. Jadi ini membatasi jenis pembatalan yang bisa terjadi. Sedangkan dalam konstruksi Ben-Atau, untuk menghitung

, kita perlu menghitung polinomial derajat

(meskipun output memiliki derajat

), dan kemudian secara krusial menggunakan pembatalan untuk menyingkirkan syarat derajat

. Ini bukan bukti, hanya intuisi ...

S_{k}^{n}

$S_k^n$

n

$n$

k < n

$k < n$

> k

$> k$

Joshua Grochow

@ Yosua: ya, kita tahu bahwa koefisien variabel

dalam polinomial

adalah polinomial persis

. Tapi kita perlu Gauss (dan begitu - subtractions) untuk mengekstrak koefisien ini dari

nilai

pada

titik yang berbeda. Pertanyaan saya menanyakan apakah "kata monoton" memang tidak memiliki Gauss , dalam hal ini. (Dengan jawaban yang sudah ditebak - TIDAK.) Saya tidak yakin bahwa untuk ini, cukup dengan menyingkirkan persyaratan derajat

y

$y$

P (y, x)

$P(y,x)$

S_{k}^{n} (x)

$S_k^n(x)$

n + 1

$n+1$

P (y)

$P(y)$

n + 1

$n+1$

> k

$> k$

k

$k$

Kompleksitas rangkaian aritmatika monoton polinomial simetris elementer?

Jawaban: