Darstellung von OR mit Polynomen

Ich weiß, dass trivialerweise die OR-Funktion für Variablen genau durch das Polynom als solches dargestellt werden kann: , das vom Grad .$n$ p ( x 1 , ... , x n ) p ( x 1 , ... , x n ) = 1 - ≤ n i = 1 ( 1 - x $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$

Aber wie könnte ich zeigen, was offensichtlich ist, dass wenn ein Polynom ist, das die OR-Funktion genau darstellt (also ), dann ?∀ x ∈ { 0 , 1 } n : p ( x ) = ⋁ n i = 1 x i ° ( p ) ≥ $p$$\forall x \in \{0,1\}^n : p(x) = \bigvee_{i = 1}^n x_i$$\deg(p) \ge n$

Sei eine Boolesche Funktion. Wenn es eine Polynomdarstellung P hat, dann hat es eine mehrlineare Polynomdarstellung Q des Grades deg Q ≤ deg P : Ersetze einfach jede Potenz x k i , wobei k ≥ 2 ist , durch x i . Wir können uns also auf mehrlineare Polynome beschränken.$f\colon \{0,1\}^n \to \{0,1\}$$P$$Q$$\deg Q \leq \deg P$$x_i^k$$k \geq 2$$x_i$

Claim: Die Polynome , als Funktionen { 0 , 1 } n → R eine Grundlage für den Raum aller Funktionen bilden { 0 , 1 } n → R .$\{ \prod_{i \in S} x_i : S \subseteq [n] \}$$\{0,1\}^n \to \mathbb{R}$$\{0,1\}^n \to \mathbb{R}$

Beweis: Wir zeigen zunächst, dass die Polynome linear unabhängig sind. Nehmen wir an, dass für alle ( x 1 , ... , x n ) ∈ { 0 , 1 } n . Wir beweisen durch (starke) Induktion am | S | dass c S = 0 . Angenommen, c T = 0 für alle | $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$ , und lassen Sie uns eine Menge S der Kardinalität k gegeben werden . Für alle T ⊂ S wissen wirdaß durch Induktion c T = 0 , und so 0 = f ( 1 S ) = c S , wobei 1 S der Eingang istdie 1 auf den Koordinaten von S .$|T| < k$$S$$k$$T \subset S$$c_T = 0$$0 = f(1_S) = c_S$$1_S$$1$$S$$~\qquad\square$

Die Behauptung zeigt, dass die mehrlineare Darstellung einer Funktion eindeutig ist (in der Tat muss f nicht einmal 0 / 1- bewertet sein). Die eindeutige mehrlineare Darstellung von OR ist 1 - ∏ i ( 1 - x i ) mit dem Grad n .$f\colon \{0,1\}^n \to \{0,1\}$$f$$0/1$$1-\prod_i(1-x_i)$$n$

Lassen ein Polynom sein , so dass für alle x ∈ { 0 , 1 } n , p ( x ) = O R ( x ) . Betrachten Sie die Symmetrisierung des Polynoms p : q ( k ) = $p$$x\in \{0,1\}^n$$p(x) = \sf{OR}(x)$$p$Da die OR-Funktion eine symmetrische Boolesche Funktion ist, gilt Folgendes fürk=1,2,…,n,q(k)=1undq(0)=0. Daq-1ein Nicht-Null-Polynom ist und mindestensn0 hat, muss es einen Grad von mindestensn haben. Deshalb,

Die Symmetrisierung wird häufig bei der Untersuchung des ungefähren Grades der Booleschen Funktionen und der Komplexität von Quantenabfragen verwendet. Siehe zum Beispiel http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf .

Yuval und Henry haben zwei verschiedene Beweise dafür geliefert. Hier ist ein dritter Beweis.

Erstens beschränken wir uns, wie in Yuvals Antwort, auf multilineare Polynome. Jetzt haben Sie bereits ein Grad Multilinearpolynom gezeigt, das der OR-Funktion entspricht. Jetzt müssen wir nur noch zeigen, dass dieses Polynom einzigartig ist, und daher haben Sie die einzige Darstellung der OR-Funktion als Polynom gefunden. Folglich ist sein Grad n .$n$$n$

Behauptung: Wenn zwei mehrlineare Polynome p und q im Hyperkubus gleich sind, sind sie überall gleich.

Beweis: Sei r (x) = p (x) - q (x), und wir wissen, dass r (x) = 0 für alle x in . Wir wollen zeigen, dass r (x) identisch Null ist. Nehmen Sie für einen Widerspruch an, dass dies nicht der Fall ist, und wählen Sie ein Monom in r mit einem Koeffizienten ungleich Null, der einen minimalen Grad aufweist. Setzen Sie alle Variablen außerhalb dieses Monoms auf 0 und alle Variablen in diesem Monom auf 1. r (x) ist in dieser Eingabe ungleich Null, aber diese Eingabe ist Boolesch, was ein Widerspruch ist.$\{0,1\}^n$