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 i 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 i ≠ 0 x i
Apakah polinomial diketahui B ( f ) lebih kecil dari 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
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 ( . 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 )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 (
, 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 ) dari Strassen dan Baur (dengan koefisien 0-1) tetap yang terbaik yang kita miliki saat ini.