Reprezentowanie OR za pomocą wielomianów

Wiem, że w trywialny sposób funkcja OR dla zmiennych może być dokładnie reprezentowana przez wielomian jako taki: , czyli stopnia .$n$$x_1,\ldots, x_n$$p(x_1,\ldots,x_n)$$p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\right)$$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 ) ≥ $p$$\forall x \in \{0,1\}^n : p(x) = \bigvee_{i = 1}^n x_i$$\deg(p) \ge n$

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\colon \{0,1\}^n \to \{0,1\}$$P$$Q$$\deg Q \leq \deg P$$x_i^k$$k \geq 2$$x_i$

Twierdzenie: Wielomiany , jako funkcje stanowią podstawę dla przestrzeni wszystkich funkcji .$\{ \prod_{i \in S} x_i : S \subseteq [n] \}$$\{0,1\}^n \to \mathbb{R}$$\{0,1\}^n \to \mathbb{R}$

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 $f = \sum_S c_S \prod_{i \in S} x_i = 0$$(x_1,\ldots,x_n) \in \{0,1\}^n$$|S|$$c_S = 0$$c_T = 0$$|T| < k$$S$$k$$T \subset S$$c_T = 0$1 S 1 $0 = f(1_S) = c_S$$1_S$$1$$S$$~\qquad\square$

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\colon \{0,1\}^n \to \{0,1\}$$f$1 - Õ i ( 1 - x i ) $0/1$$1-\prod_i(1-x_i)$$n$

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 najmniej$p$$x\in \{0,1\}^n$$p(x) = \sf{OR}(x)$$p$k=1,2,…,nq(k)=1q(0)=0q-1nnp

$$q(k) = \frac{1}{\binom{n}{k}} \sum_{x: |x| = k} p(x).$$ $k = 1, 2, \ldots, n$$q(k) = 1$$q(0) = 0$$q-1$$n$0, musi mieć stopień co najmniej . Dlatego musi mieć również stopień .$n$$p$$n$

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 .

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 .$n$$n$

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$