Schwarz-Zippel Lema

El lema de Schwartz-Zippel (también el lema de DeMillo-Lipton-Schwartz-Sippel ) es un resultado ampliamente utilizado para verificar la igualdad de polinomios , es decir, en el problema de verificar algún polinomio de muchas variables para igualdad idéntica a cero. El lema fue descubierto independientemente por Jack Schwartz [1] , Richard Zippel [2] y Richard DeMillo y Richard Lipton , aunque la versión de DeMillo y Lipton es anterior al resultado de Schwartz y Zippel [3] por un año . Una versión del lema para campos finitos fue probada por Oistin Ore en 1922 [4] .

Lema

La entrada del problema es un polinomio en variables sobre el campo . Puede darse en forma de esquema aritmético o como determinante de alguna matriz de polinomios . Por el momento, no se conocen algoritmos subexponenciales deterministas que permitan comprobar que este polinomio es distinto de cero. Sin embargo, existen algoritmos aleatorios conocidos que resuelven este problema en tiempo polinomial. Al analizarlos, generalmente se requiere estimar la probabilidad de que un polinomio distinto de cero sea igual a cero en algún punto elegido al azar. El lema de Schwartz-Zippel se formula de la siguiente manera: $norte$ $\matemáticas {F}$

Sea un polinomio de grado distinto de cero sobre el campo . Sea un subconjunto finito y deje que los elementos se elijan de manera uniforme e independiente entre sí. entonces _ $P\in F[x_{1},x_{2},\dots,x_{n}]$ $d\geq 0$ $\matemáticas {F}$ $S$ $\matemáticas {F}$ $r_{1},r_{2},\puntos,r_{n}$ $S$ $\Pr[P(r_{1},r_{2},\dots,r_{n})=0]\leq {\frac {d}{\vert S\vert }}$

Prueba

En el caso de una variable, el lema se sigue directamente del hecho de que un polinomio de grado puede tener como máximo diferentes raíces sobre el campo . $d$ $d$ $\matemáticas {F}$

El lema se puede probar en forma general por inducción matemática sobre el número de variables . El caso base se probó anteriormente. $norte$ $n=1$

Sea ahora el teorema cierto para todos los polinomios sobre variables. Se puede considerar como un polinomio en , escrito en la forma $n-1$ $PAGS$ $x_{1}$

P(x_{1},\dots,x_{n})=\sum _{i=0}^{d}x_{1}^{i}P_{i}(x_{2},\ puntos ,x_{n})

Como no es igual a cero de forma idéntica, existe algún número tal que tampoco es igual a cero. Sea el mayor de tales números. Entonces , ya que el grado no excede . $PAGS$ $i$ $Pi}$ $i$ $\deg P_{i}\leqdi$ $x_{1}^{i}P_{i}$ $d$

Que ahora se elija al azar de . Por la hipótesis de inducción, . ${\displaystyle r_{2},\puntos,r_{n))$ $S$ $\Pr[P_{i}(r_{2},\ldots,r_{n})=0]\leq {\frac {di}{|S|}}$

Si , entonces tiene un grado (y por lo tanto no es igual a cero de forma idéntica), por lo tanto $P_{i}(r_{2},\ldots,r_{n})\neq 0$ $P(x_{1},r_{2},\ldots,r_{n})$ $i$

\Pr[P(r_{1},r_{2},\ldots,r_{n})=0|P_{i}(r_{2},\ldots,r_{n})\neq 0 ]\leq {\frac{i}{|S|}}

Si designamos un evento como , un evento como y adicional a un evento como , entonces $P(r_{1},r_{2},\ldots,r_{n})=0$ $A$ $P_{i}(r_{2},\ldots,r_{n})=0$ $B$ $B$ ${\ estilo de visualización B ^ {c}}$

{\begin{alineado}\Pr[A]&=\Pr[A\cap B]+\Pr[A\cap B^{c}]\\&=\Pr[B]\Pr[A |B]+\Pr[B^{c}]\Pr[A|B^{c}]\\&\leq \Pr[B]+\Pr[A|B^{c}]\\&\ leq {\frac {di}{|S|}}+{\frac {i}{|S|}}={\frac {d}{|S|}}\end{alineado}}

■

Aplicaciones

La importancia del lema de Schwarz-Sippel y la verificación de la igualdad de polinomios se deriva de los algoritmos que se pueden reducir a este problema.

Comparación de dos polinomios

Dados dos polinomios y , ¿es cierto que $p_{1}(x)$ $p_{2}(x)$

p_{1}(x)\equiv p_{2}(x)?

Este problema se puede reducir a comprobar la igualdad de polinomios, ya que basta comprobar que

[p_{1}(x)-p_{2}(x)]\equiv 0.

Por lo tanto, si es posible determinar que

p(x)\equiv 0,

dónde

p(x)=p_{1}(x)\;-\;p_{2}(x),

entonces también es posible determinar si los dos polinomios dados son iguales.

La comparación de dos polinomios se puede utilizar en el análisis de programas ramificados . Un programa de bifurcación de lectura única se puede representar como un polinomio multilineal que evalúa (sobre algún campo) a partir de ceros y unos la misma función booleana que el programa de bifurcación. Por lo tanto, dos programas de bifurcación evalúan la misma función booleana si y solo si los polinomios correspondientes son iguales. Esto significa que verificar la igualdad de las funciones booleanas que se calculan mediante programas de lectura única con bifurcación se puede reducir a verificar la igualdad de polinomios.

Prueba de simplicidad

Dado un número , ¿es un número primo ? $n\in \mathbb {Z^{+}}$ $norte$

Manindra Agrawal y Somenath Biswas desarrollaron un algoritmo aleatorio simple utilizando pruebas de igualdad de polinomios para determinar si un número es primo . $norte$

Demostraron que todos los números primos (y solo los números primos) satisfacen la siguiente comparación: $norte$

(1+z)^{n}=1+z^{n}({\mbox{mod}}\;n).

Este resultado se deriva del endomorfismo de Frobenius .

Dejar

{\mathcal {P}}_{n}(z)=(1+z)^{n}-1-z^{n}.

Entonces si y solo si es un número primo [5] . Sin embargo, dado que puede o no ser un número primo, el método de Schwartz-Zippel no funcionará aquí. Agrawal y Biswas utilizan una técnica más sofisticada que consiste en dividir por un polinomio aleatorio reducido de pequeño grado. ${\mathcal {P}}_{n}(z)=0\;({\mbox{mod}}\;n)$ $norte$ $norte$ ${\mathcal {P}}_{n}$

Coincidencia perfecta

Dado un gráfico de $G=(V,E)$ vértices, donde es un número par. ¿Contiene una combinación perfecta ? $norte$ $norte$ $GRAMO$

El determinante de la matriz de Tutt no es un polinomio idéntico a cero si y solo si el gráfico tiene una coincidencia perfecta.

( Tutte 1947 )

Un subconjunto de un conjunto de aristas se denomina coincidencia si cada vértice de incide con como máximo una arista de . Una correspondencia se llama perfecta si cada vértice de incide con exactamente una arista de . La matriz Tatta es una matriz: $D$ $mi$ $V$ $D$ $V$ $D$ $A$

A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1{\mathit {n))}\\a_{21}&a_{22}&\cdots &a_{2{ \mathit {n}}}\\\vdots &\vdots &\ddots &\vdots \\a_{{\mathit {n}}1}&a_{{\mathit {n}}2}&\ldots &a_{\ matemática {nn}}\end{bmatrix}}

dónde

a_{ij}={\begin{casos}x_{ij}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ y }}i<j\ \-x_{ji}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ y }}i>j\\0\;\;\;\;{\ mbox{de lo contrario}}.\end{casos}}

El determinante de la matriz de Tutt (como un polinomio en ) se da como el determinante de esta matriz simétrica oblicua , que es igual al cuadrado del Pfaffiano de la matriz y es distinto de cero idénticamente si y solo si hay una coincidencia perfecta en la gráfica. $x_{ij},i<j$ $A$

Por lo tanto, utilizando la prueba de igualdad de polinomios, se puede verificar si un gráfico arbitrario contiene una coincidencia perfecta. $GRAMO$

En el caso especial de un gráfico bipartito balanceado en los vértices, la matriz de Tatta toma la forma de una matriz de bloques ${\ estilo de visualización n = m + m}$

A={\begin{pmatrix}0&X\\-X^{t}&0\end{pmatrix}}

Las primeras filas (y, en consecuencia, las columnas) están indexadas por la primera parte del gráfico bipartito y las últimas filas están indexadas por la segunda parte. En este caso, el Pfaffian (hasta un signo) coincide con el determinante habitual de la matriz de tamaño . La matriz es entonces la matriz de Edmonds del grafo bipartito dado. $metro$ $metro$ $X$ $m \veces m$ $X$

Notas

↑ ( Schwartz 1980 )
↑ ( Zippel 1979 )
↑ ( De Millo & Lipton 1978 )
↑ O. Mineral, Über höhere Kongruenzen. alfombra norsk. Forenings Skrifter Ser. I (1922), n. 7, 15 páginas.
↑ ( Agrawal 2003 )

Literatura

Agrawal, Manindra; Biswas, Somenath. Pruebas de identidad y primalidad a través del resto chino // Revista de la ACM : revista. - 2003. - vol. 50 , núm. 4 . - Pág. 429-443 . -doi : 10.1145/ 792538.792540 .
Berman, Piotr; Karpinski, Marek; Larmore, Lawrence L.; Plandowski, Wojciech; Rytter, Wojciech Sobre la complejidad de la coincidencia de patrones para textos bidimensionales altamente comprimidos // Journal of Computer and System Sciences : diario. - 2002. - vol. 65 , núm. 2 . - Pág. 332-350 . -doi : 10.1006/ jcss.2002.1852 .
Grigoriev, Dima; Karpinski, Marek. El problema de emparejamiento para grafos bipartitos con permanentes acotados polinómicamente está en NC . - 1987. - Págs. 166-172. - ISBN 978-0-8186-0807-0 . -doi : 10.1109/ SFCS.1987.56 .
Moshkovitz, Dana (2010). Una prueba alternativa del lema de Schwartz-Zippel.
De Millo, Richard A.; Lipton, Richard J.Una observación probabilística sobre la prueba de programas algebraicos // Cartas de procesamiento de información : diario. - 1978. - vol. 7 . - pág. 193-195 . - doi : 10.1016/0020-0190(78)90067-4 .
Rudich, Steven. Teoría de la Complejidad Computacional (neopr.) / AMS. - 2004. - V. 10. - (IAS/Park City Mathematics Series). - ISBN 978-0-8218-2872-4 .
Schwartz, Jack Algoritmos probabilísticos rápidos para verificación de identidades polinómicas (inglés) // Journal of the ACM : journal. - 1980. - Octubre ( vol. 27 , no. 4 ). - Pág. 701-717 . -doi : 10.1145/ 322217.322225.
Tutte, W. T. La factorización de grafos lineales (indefinidos) // J. London Math. Soc.. - 1947. - abril ( vol. 22 , no. 2 ). - S. 107-111 . -doi :/ jlms/s1-22.2.107 .
Zippel, Ricardo. Algoritmos probabilísticos para polinomios dispersos . - 1979. - vol. 72. - Pág. 216-226. — ISBN 978-3-540-09519-4 . -doi : 10.1007/ 3-540-09519-5_73 .
Zippel, Richard Una separación explícita del tiempo polinomial aleatorio relativizado y el tiempo polinomial determinista relativizado (ps) (febrero de 1989). Recuperado: 15 de junio de 2008. (indefinido)
Zippel, Ricardo. Computación Polinomial Efectiva (neopr.) / Springer. - 1993. - T. 241. - (The Springer International Series in Engineering and Computer Science). - ISBN 978-0-7923-9375-7 .

Enlaces

La curiosa historia del lema de Schwartz-Zippel , de Richard J. Lipton