Représenter OR avec des polynômes

23

Je sais que trivialement la fonction OR sur n variables x1,,xn peut être représentée exactement par le polynôme p(x1,,xn) comme tel: p(x1,,xn)=1i=1n(1xi) , qui est de degré n .

Mais comment pourrais-je montrer, ce qui semble évident, que si p est un polynôme qui représente exactement la fonction OR (donc x{0,1}n:p(x)=i=1nxi ), alors deg(p)n ?

matthon
la source
1
Parlez-vous de vrais polynômes? Ou des polynômes modulo 2? Si vous voulez parler de modulo 6 (ou d'autres nombres composites), la question devient plus intéressante.
Igor Shinkar

Réponses:

30

Soit f:{0,1}n{0,1} une fonction booléenne. S'il a une représentation polynomiale P alors il a une représentation polynomiale multilinéaire Q de degré degQdegP : il suffit de remplacer toute puissance xik , où k2 , par xi . Nous pouvons donc limiter notre attention aux polynômes multilinéaires.

Réclamation: Les polynômes , en tant que fonctions { 0 , 1 } nR forment une base de l'espace de toutes les fonctions { 0 , 1 } nR .{iSxi:S[n]}{0,1}nR{0,1}nR

Preuve: Nous montrons d'abord que les polynômes sont linéairement indépendants. Supposons que pour tous ( x 1 , , x n ) { 0 , 1 } n . Nous prouvons par (forte) induction sur | S | que c S = 0 . Supposons que c T = 0 pour tous | Tf=ScSiSxi=0(x1,,xn){0,1}n|S|cS=0cT=0 , et on nous donne un ensemble S de cardinalité k . Pour tous T S on sait par induction que c T = 0 , et si 0 = f ( 1 S ) = c S , où 1 S est l'entrée qui est une des coordonnées de S .|T|<kSkTScT=00=f(1S)=cS1S1S 

La demande montre que la représentation multilinéaire d'une fonction est unique ( en effet, f n'a même pas être 0 / 1 -Évaluées). La représentation multilinéaire unique de OR est 1 - i ( 1 - x i ) , qui a le degré n .f:{0,1}n{0,1}f0/11i(1xi)n

Yuval Filmus
la source
26

Soit un polynôme tel que pour tout x { 0 , 1 } n , p ( x ) = O R ( x ) . Considérons la symétrisation du polynôme p : q ( k ) = 1px{0,1}np(x)=OR(x)pNotez que, comme la fonction OU est une fonction booléenne symétrique, nous avons cela pourk=1,2,,n,q(k)=1etq(0)=0. Puisqueq-1est un polynôme non nul, et qu'il a au moinsn0, il doit avoir un degré au moinsn. Par conséquent,

q(k)=1(nk)x:|x|=kp(x).
k=1,2,,nq(k)=1q(0)=0q1nn doit également avoir le degré n .pn

La symétrisation est souvent utilisée dans l'étude du degré approximatif des fonctions booléennes et de la complexité des requêtes quantiques. Voir, par exemple, http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf .

Henry Yuen
la source
Il me semble que pour que votre preuve fonctionne, vous devez montrer que le degré de q est tout au plus le degré de p. Ce n'est pas clair pour moi. Comment montrez-vous cela?
matthon
Soit d = deg (p). Alors q est une somme de polynômes de degré d, donc le degré de q est au plus d.
Henry Yuen
3

Yuval et Henry ont donné deux preuves différentes de ce fait. Voici une troisième preuve.

nn

Affirmation: Si deux polynômes multilinéaires p et q sont égaux sur l'hypercube, alors ils sont égaux partout.

{0,1}n

Robin Kothari
la source