Apakah sirkuit aritmatika lebih lemah dari boolean?

12

Misalkan menunjukkan ukuran minimum dari hitung aritmatika (non-monoton) ( + , × , - ) yang menghitung polinomial multinear f yang diberikan ( x 1 , , x n ) = e E c e n i = 1 x e i iA(f)(+,×,) Dan B ( f ) menunjukkan ukuran minimum dari (non-monoton) boolean ( , , ¬ ) sirkuit menghitungversi boolean f b dari f didefinisikan oleh: f b ( x 1 , ... , x n ) = e E i : e i0 x i

f(x1,,xn)=eEcei=1nxiei,
B(f)(,,¬) fbf
fb(x1,,xn)=eE i:ei0xi.
Apakah polinomial diketahui B ( f ) lebih kecil dari A ( f ) ? fB(f)A(f)

Jika kita menganggap versi monoton dari rangkaian - tanpa Minus dan tidak Tidak ( ¬ ) gerbang - maka B ( f ) bahkan bisa secara eksponensial lebih kecil dari A ( f ) : ambil, misalnya, jalur terpendek polinomial f pada K n ; maka B ( f ) = O ( n 3 ) dan A ( f ) = 2 Ω ( n()(¬)B(f)A(f)fKnB(f)=O(n3)A(f)=2Ω(n)A(f)


CATATAN (2016/03/15) Dalam pertanyaan saya, saya tidak ditentukan bagaimana koefisien besar diperbolehkan. Igor Sergeev ingat saya bahwa, misalnya, berikut (univariat) polinomial f ( z ) = Σ m j = 1 2 2 j m z j memiliki A ( f ) = Ω ( m 1 / 2 ) (Strassen dan orang-orang nya kelompok). Tapi B ( f ) = 0 untuk polinomial ini, karena f b (cef(z)=j=1m22jmzjA(f)=Ω(m1/2)B(f)=0 . Kita dapat memperoleh fron f suatumultivariatpolinomial f ' ( x 1 , ... , x n ) dari n = log m variabel menggunakan menggunakan Kronecker substitusi. Kaitkan dengan setiap eksponen j a monomial X j = i : a i = 1 x i , di mana ( a 1 , , a n )fb(z)=zff(x1,,xn)n=logmjXj=i:ai=1xi(a1,,an)adalah 0-1 koefisien representasi biner dari . Kemudian diinginkan polinomial yaitu f ' = Σ m j = 1 c j X j , dan kita mendapati bahwa A ( f ' ) + n A ( f ) = Ω ( m 1 / 2 ) = 2 Ω ( n ) . Tetapi versi boolean dari f hanyalah OR dari variabel, jadi B (jf=j=1mcjXj
A(f)+nA(f)=Ω(m1/2)=2Ω(n).
f , dan kami memiliki kesenjangan yang bahkan eksponensial. Dengan demikian, jika besarnya koefisien dapat menjadi tiga-eksponensial dalam jumlah n variabel maka kesenjangan A ( f ) / B ( f ) dapatditunjukkan bahkan eksponensial. (Sebenarnya, bukan besarnya itu sendiri - lebih banyak ketergantungan aljabar dari koefisien.) Inilah mengapa masalah sebenarnya dengan A ( f ) adalah kasuskoefisienkecil(idealnya, hanya 0-1). Tetapi dalam kasus ini, seperti yang diingat Yosua, batas bawah A ( f )B(f)n1nA(f)/B(f) A(f) dari Strassen dan Baur (dengan koefisien 0-1) tetap yang terbaik yang kita miliki saat ini.A(f)=Ω(nlogn)

Stasys
sumber

Jawaban:

9

VP0VNP0

Ω(nlogn)i=1nxinΩ(nlogn)x1x2xn

Joshua Grochow
sumber
Hai Joshua: Anda benar, permanen adalah contoh (meskipun bersyarat)! Kita tidak tahu ada batas bawah pada A (f) untuk permanen. Tetapi jika versi VP dan VNP yang bebas-konstan berbeda, maka kita tahu pemisahan B (f) vs A (f) tanpa mengetahui batas (aktual).
Stasys
2
Ω(nlogn)
1
di Joshua: benar, poin bagus lagi. Jika f adalah jumlah dari kekuatan ke-n dari semua n variabel tunggal, maka B (f) paling banyak n, dan Baur-Strassen menunjukkan A (f) setidaknya sekitar n kali logaritma n. Ini adalah yang paling dikenal untuk A (f). Jadi, kesenjangan eksplisit terbesar yang diketahui untuk pertanyaan saya memang hanya logaritmik. (Sebuah pertanyaan samping: apakah Anda tahu mengapa @ saya selalu menghilang dalam komentar?)
Stasys
@Stasys: Contoh yang bagus. (Re: selain. Saya tidak. Saya pikir sistem melakukan beberapa inferensi otomatis tentang siapa hal-hal "at-ed", dan jika Anda mengarahkan pesan pada "orang default", maka itu menghapusnya. Saya pikir .)
Joshua Grochow
Baik. Penulis posting selalu diberitahu tentang komentar baru, sehingga sistem menghapus pemberitahuan @ eksplisit sebagai berlebihan.
Emil Jeřábek 3.0