Darstellung von OR mit Polynomen

23

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 ix1,,xnp(x1,,xn) np(x1,,xn)=1-ich=1n(1-xich)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 ) npx{0,1}n:p(x)=ich=1nxichdeg(p)n

matthon
quelle
1
Sprechen Sie über echte Polynome? Oder Polynome Modulo 2? Wenn Sie über Modulo 6 (oder andere zusammengesetzte Zahlen) sprechen möchten, wird die Frage interessanter.
Igor Shinkar

Antworten:

30

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:{0,1}n{0,1}PQ.degQ.degPxichkk2xich

Claim: Die Polynome , als Funktionen { 0 , 1 } nR eine Grundlage für den Raum aller Funktionen bilden { 0 , 1 } nR .{ichSxich:S[n]}{0,1}nR{0,1}nR

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 | Tf=ScSichSxich=0(x1,,xn){0,1}n|S|cS=0cT=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|<kSkTScT=00=f(1S)=cS1S1S 

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:{0,1}n{0,1}f0/11-ich(1-xich)n

Yuval Filmus
quelle
26

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 ) = 1px{0,1}np(x)=OR(x)pDa 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,

q(k)=1(nk)x:|x|=kp(x).
k=1,2,,nq(k)=1q(0)=0q-1nn muss auch Grad n haben .pn

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 .

Henry Yuen
quelle
Es scheint mir, dass Sie, damit Ihr Beweis funktioniert, zeigen müssen, dass der Grad von q höchstens der Grad von p ist. Das ist mir nicht klar. Wie zeigst du das?
Matthon
Sei d = deg (p). Dann ist q eine Summe von Polynomen des Grades d, daher ist der Grad von q höchstens d.
Henry Yuen
3

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 .nn

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

Robin Kothari
quelle