Representando la función booleana por un polinomio

10

Supongamos que tenemos una función booleana de . Está claro que un polinomio multivariado real p ( x ) tal que f ( x ) = p ( x ) en x { 0 , 1 } n puede ser multilineal. ¿Cuáles son algunas clases interesantes de funciones booleanas para las cuales el grado mínimo de p ( x )f:{0,1}n{0,1}p(x)f(x)=p(x)x{0,1}np(x)¿es conocida? ¿Tenemos ejemplos concretos?

T ....
fuente
1
Si no está familiarizado con él, hay mucho trabajo relacionado con el "grado aproximado", que pregunta, ¿cuál es el grado mínimo de un polinomio que "se aproxima" a ? No sé lo suficiente como para dar referencias específicas, pero otros sí. f
usul

Respuestas:

10

n

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

dd2dd=1

Yuval Filmus
fuente
Este es un punto útil. ¿Cuál es una buena referencia para este tema?
T ....
3
Puedes echar un vistazo al reciente libro de Ryan O'Donnell, Análisis de las funciones booleanas.
Yuval Filmus
0

Las clases de funciones booleanas con presentación multilínea única contienen

  1. Funciones pseudobooleanas sobre reales (Teorema 1.34 [1])

  2. [0,1]n

Antecedentes

"Cada función booleana puede ser representada por una forma normal disyuntiva y por una forma normal conjuntiva". (Teorema 1.4 (p.16 [1])

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

y sus aplicaciones contienen

Referencias

[1] Teoría de funciones booleanas, algoritmos y aplicaciones (Yves Crama, Peter L. Hammer, 2011)

hhh
fuente
1
Si obviamente. Ahora, ¿cómo responde eso a la pregunta?
Emil Jeřábek