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 ) 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 ) ≥ n
Jawaban:
Biarkanf: { 0 , 1 }n→ { 0 , 1 } menjadi fungsi boolean. Jika memiliki representasi polinomial P maka ia memiliki representasi polinomial multilinear Q derajat degQ ≤ degP : ganti saja daya xksaya , di mana k ≥ 2 , dengan xsaya . Jadi kita bisa membatasi perhatian kita pada polinomial multilinear.
Klaim: The polinomial , sebagai fungsi { 0 , 1 } n → R membentuk dasar untuk ruang dari semua fungsi { 0 , 1 } n → R .{ ∏i ∈ Sxsaya: S⊆ [ n ] } { 0 , 1 }n→ R { 0 , 1 }n→ R
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= ∑ScS∏i ∈ Sxsaya= 0 ( x1, ... , xn) ∈ { 0 , 1}n |S| cS= 0 cT= 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| <k S k T⊂ S cT= 0 0 =f( 1S) = cS 1S 1 S □
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 } f 0 / 1 1 - ∏saya( 1 - xsaya) n
sumber
Misalkan adalah polinomial sehingga untuk semua x ∈ { 0 , 1 } n , p ( x ) = O R ( x ) . Pertimbangkan simetri polinomial p : q ( k ) = 1p x∈{0,1}n p(x)=OR(x) p Perhatikan 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,
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 .
sumber
Yuval dan Henry telah memberikan dua bukti berbeda dari fakta ini. Ini bukti ketiga.
Klaim: Jika dua polinomial multinear, p dan q sama pada hypercube, maka keduanya sama di mana-mana.
sumber