Darstellung der Booleschen Funktion durch ein Polynom

10

Angenommen, wir haben eine boolesche Funktion aus . Es ist klar, dass ein reales multivariates Polynom p ( x ), so dass f ( x ) = p ( x ) auf x { 0 , 1 } n ist, multilinear sein kann. Was sind einige interessante Klassen von Booleschen Funktionen, für die der minimale Grad von p ( x )f:{0,1}n{0,1}p(x)f(x)=p(x)x{0,1}np(x)ist bekannt? Haben wir konkrete Beispiele?

T ....
quelle
2
Siehe auch
Andrej Bauer
1
Wenn Sie nicht damit vertraut sind, gibt es viele Arbeiten zum "ungefähren Grad", bei denen gefragt wird, wie hoch der minimale Grad eines Polynoms ist, das "approximiert" . Ich weiß nicht genug, um spezifische Referenzen zu geben, aber andere würden es tun. f
Usul

Antworten:

10

n

x{0,1}n(1)ixif(x)0
fx1xn(1)xi=1xi2f1xi2i1xi2ixi

dd2dd=1

Yuval Filmus
quelle
Dies ist ein nützlicher Punkt. Was ist eine gute Referenz für dieses Thema?
T ....
3
Sie können sich Ryan O'Donnells jüngstes Buch Analysis of Boolean functions ansehen.
Yuval Filmus
0

Klassen von Booleschen Funktionen mit eindeutiger mehrliniger Darstellung enthalten

  1. Pseudo-Boolesche Funktionen über Real (Satz 1.34 [1])

  2. [0,1]n

Hintergrund

"Jede Boolesche Funktion kann durch eine disjunktive Normalform und durch eine konjunktive Normalform dargestellt werden." (Satz 1.4 (S.16 [1])

(xx¯)(x(1x))cxFBnP(N)f(x1,,xn)=AP(N)c(A)iAxi

und ihre Anwendungen enthalten

Verweise

[1] Theorie, Algorithmen und Anwendungen boolescher Funktionen (Yves Crama, Peter L. Hammer, 2011)

hhh
quelle
1
Ja offensichtlich. Wie beantwortet das die Frage?
Emil Jeřábek