Reprezentowanie OR za pomocą wielomianów

23

Wiem, że w trywialny sposób funkcja OR dla zmiennych może być dokładnie reprezentowana przez wielomian jako taki: , czyli stopnia .nx1,,xnp(x1,,xn)p(x1,,xn)=1i=1n(1xi)n

Ale jak mogę pokazać, co wydaje się oczywiste, że jeśli jest wielomianem, który dokładnie reprezentuje funkcję OR (więc ), a następnie ?x { 0 , 1 } n : p ( x ) = n i = 1 x i deg ( p ) npx{0,1}n:p(x)=i=1nxideg(p)n

matthon
źródło
1
Czy mówisz o prawdziwych wielomianach? A może wielomian modulo 2? Jeśli chcesz porozmawiać o modulo 6 (lub innych liczbach zespolonych), pytanie staje się bardziej interesujące.
Igor Shinkar

Odpowiedzi:

30

Niech będzie funkcją logiczną. Jeśli ma wielomianową reprezentację to ma wieloliniową wielomianową reprezentację stopnia : wystarczy zastąpić dowolną potęgę , gdzie , przez . Możemy więc ograniczyć naszą uwagę do wielomianów wielomianowych.f:{0,1}n{0,1}PQdegQdegPxikk2xi

Twierdzenie: Wielomiany , jako funkcje stanowią podstawę dla przestrzeni wszystkich funkcji .{iSxi:S[n]}{0,1}nR{0,1}nR

Dowód: Najpierw pokazujemy, że wielomiany są liniowo niezależne. Załóżmy, że dla wszystkich . Udowadniamy (silną) indukcjąże . Załóżmy, że dla wszystkich , i dajmy sobie zbiór liczności . Dla wszystkich wiadomo przez indukcję, że , a więc gdzie jest wejście co o współrzędnych . ( x 1 , , x n ) { 0 , 1 } n | S | c S = 0 c T = 0 | T | < k S k T S c T = 0 0 = f ( 1 Sf=ScSiSxi=0(x1,,xn){0,1}n|S|cS=0cT=0|T|<kSkTScT=01 S 1 S.0=f(1S)=cS1S1S 

Twierdzenie pokazuje, że reprezentacja wieloliniowa funkcji jest unikalna (w rzeczywistości, nawet nie musi być oceniana na ) . Unikalna wieloliniowa reprezentacja OR to , która ma stopień .f 0 /f:{0,1}n{0,1}f1 - Õ i ( 1 - x i ) N0/11i(1xi)n

Yuval Filmus
źródło
26

Niech będzie wielomianem takim, że dla wszystkich x { 0 , 1 } n , p ( x ) = O R ( x ) . Rozważ symetrię wielomianu p : Zauważ, że ponieważ funkcja OR jest symetryczną funkcją logiczną, mamy ją dla , i . Ponieważ jest niezerowym wielomianem i ma co najmniejpx{0,1}np(x)=OR(x)pk=1,2,,nq(k)=1q(0)=0q-1nnpn

q(k)=1(nk)x:|x|=kp(x).
k=1,2,,nq(k)=1q(0)=0q1n0, musi mieć stopień co najmniej . Dlatego musi mieć również stopień .npn

Symetryzacja jest często stosowana w badaniu przybliżonego stopnia funkcji boolowskich i złożoności kwantowych zapytań. Patrz na przykład http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf .

Henry Yuen
źródło
Wydaje mi się, że aby twój dowód zadziałał, musisz pokazać, że stopień q wynosi co najwyżej stopień p. To nie jest dla mnie jasne. Jak to pokazujesz?
matthon
Niech d = deg (p). Zatem q jest sumą wielomianów stopnia d, stąd stopień q wynosi co najwyżej d.
Henry Yuen
3

Yuval i Henry podali dwa różne dowody tego faktu. Oto trzeci dowód.

Po pierwsze, podobnie jak w odpowiedzi Yuvala, ograniczamy naszą uwagę do wielomianów wielomianowych. Teraz pokazałeś już wielomianowy stopień wielomianowy, który jest równy funkcji OR. Teraz wszystko, co musimy wykazać, to to, że ten wielomian jest unikalny, a zatem znalazłeś jedyną reprezentację funkcji OR jako wielomianu. W związku z tym jego stopień wynosi .nnn

Twierdzenie: Jeśli dwa wielomianowe wielomiany p i q są równe w hipersześcianie, to są one równe wszędzie.

Dowód: Niech r (x) = p (x) - q (x) i wiemy, że r (x) = 0 dla wszystkich x w . Chcemy pokazać, że r (x) jest identycznie zerowe. W kierunku sprzeczności, załóżmy, że tak nie jest, i wybierz dowolny monomial wr o niezerowym współczynniku, który ma minimalny stopień. Ustaw wszystkie zmienne poza tym monomialem na 0, a wszystkie zmienne w tym monomialu na 1. r (x) jest niezerowe na tym wejściu, ale to wejście jest logiczne, co jest sprzecznością.{0,1}n

Robin Kothari
źródło