Una manera eficaz para comprobar el coeficiente de $x_1 x_2...x_n$ en el producto de $m$ polinomios

Question

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 ?

Answer 1

He aquí la prueba de la complejidad. Todavía estoy interesado en sugerencias para los diferentes enfoques creativos para resolver el problema (incluso soluciones parciales) y/o de las ideas o referencias para otras posibles aplicaciones.

Para dar una breve prueba, voy a reducir un problema que fue previamente publicado aquí y respondidas por Yuval Filmus a este nuevo problema.

El primer paso es un simple cambio de variable: $X' = 2X-1$ que se aplica a todas las variables de entrada. De modo que las entradas son ahora definidos sobre los $\left \{ -1,1 \right \}$ en lugar de $\left \{ 0,1 \right \}$. Por lo tanto ahora tenemos $X'^2=1$ en lugar de $X^2=X$. Alternativamente, se podría utilizar directamente la transformación descrita en el problema para obtener los polinomios. Para 3SAT problema, solo necesitamos la transformación polinómica de los siguientes tres funciones:

\begin{matrix} \text{Gate Name} & \text{Boolean} & \text{Polynomial} \\ XOR (y=\neg{x})& xy'+x'y& 1-XY\\ AllOrNone (x=y=z)& xyz+x'y'z' &1+XY+XZ+YZ\\ atLeastOne (x\lor y \lor z)& (x'y'z')' &7+ X + Y + Z -XY-XZ-YZ+ XYZ \end{de la matriz}

El segundo paso es multiplicar $F$$X_1 X_2 ... X_n$. Esto va a cambiar a todos los poderes de uno y convertirlo $F = a X^2 + b X + c$$F = a X^3 + b X^2 + c X \equiv (a+c) X + b$. No sería difícil mostrar que $a+c$ es, de hecho, el número total de soluciones de ($F(X=1)$ es el número de soluciones con $x$ $F(X=-1)$ es el número de soluciones con $\neg{x}$) y será igual a cero si y sólo si el conjunto original de ecuaciones no válido. Tenga en cuenta que, en la práctica, para cada variable $X_i$, podemos elegir uno de los polinomios (cláusula) con $X_i$, se multiplica por $X_i$ y convertir $X_i^2$ $1$para que la cláusula. Esto reducirá la 3SAT problema el problema que se describe en esta pregunta. En los cálculos anteriores, he utilizado la multiplicación por una constante para la simplificación, pero que no afecta a los resultados.

Answer 2

Esta es una matriz de Hadamard de Sylvester tipo, escritas en un orden diferente. Existe una enorme literatura sobre este tema.

Sólo utilice el $[1,X,Y,XY,Z,ZX,ZY,ZXY]$ que corresponde a lexicográfica del orden a través de los números enteros, y aplicar la permutación correspondiente a las columnas así.

Ryan O'Donnell notas sobre el Análisis de funciones Booleanas disponible aquí que ahora son publicados como un libro, Claude Carlet capítulos de la Booleanos funciones de aquí son fácilmente accesibles en línea.

En el orden que me dio anteriormente, su matriz es simplemente el 3 veces producto de Kronecker $$H_2 \otimes H_2\otimes H_2$$ de la básica, de 2 en 2 matriz de Hadamard.

$$H_2=\left(\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array} \right),$$

Este documento considera la evaluación eficiente de Hadamard representación de los coeficientes.