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 )¿es conocida? ¿Tenemos ejemplos concretos?
boolean-functions
T ....
fuente
fuente
Respuestas:
fuente
Las clases de funciones booleanas con presentación multilínea única contienen
Funciones pseudobooleanas sobre reales (Teorema 1.34 [1])
Antecedentes
y sus aplicaciones contienen
(circuitos) Complejidad de la computación polinómica multilínea Función booleana
(análisis de Fourier) Límites inferiores para polinomios que calculan las funciones booleanas
Referencias
[1] Teoría de funciones booleanas, algoritmos y aplicaciones (Yves Crama, Peter L. Hammer, 2011)
fuente