Tenemos $n$ variables $x_1, ..., x_n$ $m$ polinomios $f_1, ..., f_m$.
El grado máximo de cada variable $x_i$ en cada polinomio $f_j$$1$.
Además, cada variable está presente en la mayoría de los dos de los polinomios y cada polinomio contiene un máximo de 3 de las variables.
Definimos $F$ como el producto de todos los polinomios: $F=f_1*f_2*...*f_n$ .
Nos interesa conocer si un determinado plazo ($x_1 x_2...x_n$) aparece en $F$ o no. En otras palabras, si el coeficiente de $x_1 x_2...x_n$ sería distinto de cero si estamos totalmente de expandir $F$. Es allí una manera eficiente para comprobar eso?
He aquí un ejemplo:
$f_1 = (5 x + 3 x y - z)$
$f_2 = (- x y + 2 y )$
$f_3 = (z -3)$
$F = f_1 f_2 f_3 = (5 x + 3 x y - z)(- x y + 2 y)(z -3)$
$F = -30 x y+15 x^2 y-18 x y^2+9 x^2 y^2+6 y z+7 x y z-5 x^2 y z+6 x y^2 z-3 x^2 y^2 z-2 y z^2+x y z^2$
Estamos interesados en saber si es o no el coeficiente de $xyz$ es cero. En el ejemplo anterior, no es cero y es igual a $7$. Es allí una manera eficiente de hacerlo (al menos para algunos no trivial casos especiales) que es aplicable a los casos con, por ejemplo, $n=300$ variables e $m=200$ polinomios.
Fondo: Aquí hay alguna información de fondo acerca de los orígenes de este problema para el lector interesado:
Dada cualquier función booleana en 3 variables, podemos representar con un vector binario en una de las 8 dimensiones del espacio con entidades igual a 1 si la función devuelve TRUE para que la combinación de entradas. (es decir, estándar de la suma de los productos de la forma)
Se podría utilizar la siguiente matriz lineal del mapa el espacio de las funciones booleanas a un nuevo espacio que puede ser representada con polinomios en 3 variables:
La anterior matriz se define una transformación reversible (booleano de dominio para el polinomio de dominio) con varias características muy interesantes, algunos de los enumerados a continuación:
i) de la Fila $X$ sólo depende de $x$, y es $1$ en columnas con $x$ $-1$ en columnas con $x'$ (complemento de $x$).
ii) de la Fila $XY$ es el elemento por elemento producto de la fila $X$ y la de la fila $Y$. (y sólo depende de $X$$Y$, o más específicamente $x \mathbin{\oplus} y$).
iii) El producto interior de cada par de filas (o columnas) es cero (ortogonales).
iv) Todos los elementos son 1 y -1 (para normalizada $w$ $\frac{1}{\sqrt{2^n}}$ $\frac{-1}{\sqrt{2^n}}$ donde $n$ # de variables)
v) de la Matriz es simétrica, por lo $w'=w$ y para normalizada $w$, tenemos $w^{-1}$=$w$. (La inversa de la transformación y el avance de transformación sólo se diferencian en un factor constante $\frac{1}{2^n}$).
vi) Cualquier función booleana de tres (o, en general,$n$) variables, podría ser representado por un vector binario $u$ donde $u_i$ es 1 si y sólo si $f$ es CIERTO para la correspondiente combinación de entradas.
vii) por otra parte, si tenemos dos funciones de $f_1$ y $f_2$, $f_{12}=f_1 \land f_2$ está representado por $u_{12}=u_1 * u_2$ donde, $*$ es el elemento por elemento del producto. A continuación,$v_{12}=w.u_{12}=w(u_1 *u_2)$. (no es igual a $w u_1 * w u_2$, sin embargo se puede realizar regular la multiplicación de polinomio de dominio sólo necesitará reemplazar cualquier $x^2$ $1$ al final y será equivalente a $\land$ booleanas de dominio. Tenga en cuenta que dado (iv), en la plaza de cualquier fila será igual a la fila $1$)
viii) de la misma forma con tres funciones de $f_{123}=f_1 \land f_2 \land f_3$, tenemos $u_{123}=u_1*u_2*u_3$, $v_{123}=w(u_1*u_2*u_3)$
ix) Si multiplicamos $F$ $X$ en el polinomio de dominio, en booleana de dominio de todos los términos con $x$ será multiplicado por el $1$ y todos los términos con $x'$ será multiplicado por el $-1$.
x) $F(X=0)$ en el polinomio de dominio da el número de soluciones de ($1$ elementos) en booleana de dominio. Del mismo modo, el coeficiente de $X$ en el polinomio de dominio es el número de soluciones con $x=TRUE$ menos el número de soluciones con $x=FALSE$. Del mismo modo que el coeficiente de $XY$ es el número de soluciones con $xy$ ponderado por la paridad (es decir, $xy$ $x'y'$ soluciones son contados con signo positivo y $xy'$ $x'y$ soluciones son contados con signo negativo). Esto también es consecuencia directa de la i y ii.
Hay alguna buena referencia para esta transformación? Es conocido por los nombres de lo que puedo ver? Todas las ideas para posibles aplicaciones? Mi motivación fue que el uso de estas bases ortogonales, uno podría simplificar algunos cálculos en la transformada de dominio (por ejemplo, desarrollar más rápido los algoritmos para la solución de SAT o simplificar circuitos lógicos utilizando algebraicas y no algebraicas métodos).
Para probar si un conjunto de ecuaciones booleanas son al mismo tiempo conste, se podría transformar a los polinomios, ampliar, sustituir todas las $x_i^2$ $1$ y comprobar si el resto es cero absoluto o no. Para hacerlo de manera más eficiente, se podría establecer $x_i$ a cero para eliminar algunos intermedio términos de la expansión.
Por ejemplo, supongamos $x_i$ sólo está presente en $f_1=a x_i +b$$f_2 = c x_i +d$, la expansión de $x_i$ y la eliminación de $x_i$ utilizando el método anterior sería el rendimiento:
$F = f_1 f_2 f_3 ... f_m = (a x_i +b)(c x_i +d)f_3 ... f_m =(ac x_i^2 +(bc+ad) x_i +bd)f_3 ... f_m \\ \equiv (ac+bd) f_3 ... f_m$
Luego se puede continuar con la eliminación de las otras variables. Después de la eliminación de todas las variables, el resto se dará el número total de soluciones que satisfacen todas las ecuaciones simultáneamente. Es allí una manera eficiente para obtener la solución para algún subconjunto de los casos, sin la necesidad de exponencial cálculos ?
