Representando OR con polinomios

23

Sé que trivialmente la función OR en n variables x1,,xn puede representarse exactamente por el polinomio p(x1,,xn) como tal: p(x1,,xn)=1i=1n(1xi) , que es de grado n .

Pero, ¿cómo podría mostrar, lo que parece obvio, que si p es un polinomio que representa la función OR exactamente (entonces x{0,1}n:p(x)=i=1nxi ), entonces deg(p)n ?

Matthon
fuente
1
¿Estás hablando de polinomios reales? ¿O polinomios módulo 2? Si desea hablar sobre el módulo 6 (u otros números compuestos), la pregunta se vuelve más interesante.
Igor Shinkar

Respuestas:

30

Sea una función booleana. Si tiene una representación polinomial P, entonces tiene una representación polinomial multilineal Q de grado deg Q deg P : simplemente reemplace cualquier potencia x k i , donde k 2 , por x i . Entonces podemos restringir nuestra atención a polinomios multilineales.f:{0,1}n{0,1}PQdegQdegPxikk2xi

Reclamación: Los polinomios , como las funciones de { 0 , 1 } nR formar una base de por el espacio de todas las funciones de { 0 , 1 } nR .{iSxi:S[n]}{0,1}nR{0,1}nR

Prueba: Primero mostramos que los polinomios son linealmente independientes. Suponga que para todos ( x 1 , , x n ) { 0 , 1 } n . Probamos por (fuerte) inducción en | S | que c S = 0 . Supongamos que c T = 0 para todos | Tf=ScSiSxi=0(x1,,xn){0,1}n|S|cS=0cT=0 , y se nos dará un conjunto S de cardinalidad k . Para todos T S sabemos por inducción que c T = 0 , y así 0 = f ( 1 S ) = c S , donde 1 S es la entrada que es 1 de las coordenadas de S .|T|<kSkTScT=00=f(1S)=cS1S1S 

La reclamación muestra que la representación multilineal de una función es único (de hecho, f no siquiera tiene que ser 0 / 1 -valued). La representación multilineal única de OR es 1 - i ( 1 - x i ) , que tiene un grado n .f:{0,1}n{0,1}f0/11i(1xi)n

Yuval Filmus
fuente
26

Sea un polinomio tal que para todo x { 0 , 1 } n , p ( x ) = O R ( x ) . Considere la simetrización del polinomio p : q ( k ) = 1px{0,1}np(x)=OR(x)pTenga en cuenta que, dado que la función OR es una función booleana simétrica, tenemos que parak=1,2,...,n,q(k)=1yq(0)=0. Comoq-1es un polinomio distinto de cero y tiene al menosn0, debe tener un grado de al menosn. Por lo tanto,

q(k)=1(nk)x:|x|=kp(x).
k=1,2,,nq(k)=1q(0)=0q1nn también debe tener grado n .pn

La simetrización se usa a menudo en el estudio del grado aproximado de funciones booleanas y la complejidad de la consulta cuántica. Ver, por ejemplo, http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf .

Henry Yuen
fuente
Me parece que para que su prueba funcione, debe demostrar que el grado de q es como máximo el grado de p. Esto no está claro para mí. ¿Cómo se muestra esto?
matthon
Deje d = deg (p). Entonces q es una suma de polinomios de grado d, por lo tanto, el grado de q es como máximo d.
Henry Yuen
3

Yuval y Henry han dado dos pruebas diferentes de este hecho. Aquí hay una tercera prueba.

nn

Reclamación: Si dos polinomios multilineales p y q son iguales en el hipercubo, entonces son iguales en todas partes.

{0,1}n

Robin Kothari
fuente