Mewakili ATAU dengan polinomial

23

Saya tahu bahwa secara sepintas fungsi OR pada variabel dapat direpresentasikan dengan tepat oleh polinomial seperti: , yang bertingkat .x 1 , ... , x n p ( x 1 , ... , x n ) p ( x 1 , ... , x n ) = 1 - n i = 1 ( 1 - x i ) nnx1,,xnp(x1,,xn)p(x1,,xn)=1i=1n(1xi)n

Tapi bagaimana saya bisa menunjukkan, apa yang tampak jelas, bahwa jika adalah polinomial yang mewakili fungsi OR dengan tepat (jadi ), lalu ?x { 0 , 1 } n : p ( x ) = n i = 1 x i deg ( p ) npx{0,1}n:p(x)=i=1nxideg(p)n

matthon
sumber
1
Apakah Anda berbicara tentang polinomial nyata? Atau polinomial modulo 2? Jika Anda ingin berbicara tentang modulo 6 (atau angka komposit lainnya), maka pertanyaannya menjadi lebih menarik.
Igor Shinkar

Jawaban:

30

Biarkan f:{0,1}n{0,1} menjadi fungsi boolean. Jika memiliki representasi polinomial P maka ia memiliki representasi polinomial multilinear Q derajat degQdegP : ganti saja daya xik , di mana k2 , dengan xi . Jadi kita bisa membatasi perhatian kita pada polinomial multilinear.

Klaim: The polinomial , sebagai fungsi { 0 , 1 } nR membentuk dasar untuk ruang dari semua fungsi { 0 , 1 } nR .{iSxi:S[n]}{0,1}nR{0,1}nR

Bukti: Pertama-tama kami menunjukkan bahwa polinomial bebas linear. Misalkan untuk semua ( x 1 , , x n ) { 0 , 1 } n . Kami membuktikan dengan induksi (kuat) di | S | bahwa c S = 0 . Misalkan c T = 0 untuk semua | Tf=ScSiSxi=0(x1,,xn){0,1}n|S|cS=0cT=0 , dan mari kita diberi satu set S kardinalitas k . Untuk semua T S kita tahu dengan induksi yang c T = 0 , dan sebagainya 0 = f ( 1 S ) = c S , di mana 1 S adalah masukan yang 1 pada koordinat S .|T|<kSkTScT=00=f(1S)=cS1S1S 

Klaim menunjukkan bahwa representasi multilinear dari fungsi unik (memang, f bahkan tidak harus 0 / 1 -valued). Representasi multilinear unik OR adalah 1 - i ( 1 - x i ) , yang memiliki derajat n .f:{0,1}n{0,1}f0/11i(1xi)n

Yuval Filmus
sumber
26

Misalkan adalah polinomial sehingga untuk semua x { 0 , 1 } n , p ( x ) = O R ( x ) . Pertimbangkan simetri polinomial p : q ( k ) = 1px{0,1}np(x)=OR(x)pPerhatikan bahwa, karena fungsi OR adalah fungsi boolean simetris, kami memilikinya untukk=1,2,,n,q(k)=1, danq(0)=0. Karenaq-1adalah polinomial non-nol, dan memiliki setidaknyan0, ia harus memiliki derajat setidaknyan. Karena itu,

q(k)=1(nk)x:|x|=kp(x).
k=1,2,,nq(k)=1q(0)=0q1nn juga harus memiliki gelar n .pn

Symmetrization sering digunakan dalam studi tentang perkiraan tingkat fungsi boolean dan kompleksitas kueri kuantum. Lihat, misalnya, http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf .

Henry Yuen
sumber
Tampak bagi saya bahwa agar bukti Anda bekerja, Anda perlu menunjukkan bahwa tingkat q paling banyak adalah tingkat p. Ini tidak jelas bagi saya. Bagaimana Anda menunjukkan ini?
matthon
Misalkan d = deg (p). Maka q adalah jumlah derajat d polinomial, maka tingkat q paling banyak adalah d.
Henry Yuen
3

Yuval dan Henry telah memberikan dua bukti berbeda dari fakta ini. Ini bukti ketiga.

nn

Klaim: Jika dua polinomial multinear, p dan q sama pada hypercube, maka keduanya sama di mana-mana.

{0,1}n

Robin Kothari
sumber