En matemáticas, el lema de Schwartz-Zippel (también llamado lema de DeMillo-Lipton-Schwartz-Zippel ) es una herramienta comúnmente utilizada en la prueba de identidad polinomial probabilística , es decir, en el problema de determinar si un polinomio multivariado dado es el polinomio 0 [ aclaración necesario ] (o idénticamente igual a 0). Fue descubierto de forma independiente por Jack Schwartz , [1] Richard Zippel , [2] y Richard DeMillo y Richard J. Lipton , aunque la versión de DeMillo y Lipton se mostró un año antes del resultado de Schwartz y Zippel. [3]La versión de campo finito de este límite fue probada por Øystein Ore en 1922. [4]
Declaración y prueba del lema
Teorema 1 (Schwartz, Zippel). Dejar
ser un polinomio distinto de cero de grado total d ≥ 0 sobre un campo F. Sea S un subconjunto finito de F y sea r 1 , r 2 , ..., r n seleccionado al azar de forma independiente y uniforme de S. Entonces
En el caso de una sola variable, esto se deriva directamente del hecho de que un polinomio de grado d no puede tener más de d raíces.
Prueba. La demostración es por inducción matemática en n . Para n = 1 , como se mencionó anteriormente, P puede tener como máximo d raíces. Esto nos da el caso base. Ahora, suponga que el teorema es válido para todos los polinomios en n - 1 variables. Entonces podemos considerar que P es un polinomio en x 1 escribiéndolo como
Dado que P no es idénticamente 0, hay algo de i tal queno es idénticamente 0. Tome el mayor de estos i . Luego, ya que el grado de es como máximo d.
Ahora elegimos al azar de S . Por la hipótesis de inducción,
Si , luego es de grado i (y por lo tanto no idénticamente cero) por lo que
Si denotamos el evento por A , el eventopor B , y el complemento de B por, tenemos
Aplicaciones
La importancia del teorema de Schwartz-Zippel y la prueba de identidades polinomiales se deriva de los algoritmos que se obtienen a problemas que pueden reducirse al problema de las pruebas de identidad polinomial .
Prueba cero
Por ejemplo, es
Para resolver esto, podemos multiplicarlo y verificar que todos los coeficientes sean 0. Sin embargo, esto lleva un tiempo exponencial . En general, un polinomio se puede representar algebraicamente mediante una fórmula aritmética o un circuito .
Comparación de dos polinomios
Dado un par de polinomios y , es
- ?
Este problema puede resolverse reduciéndolo al problema de la prueba de identidad polinomial. Equivale a comprobar si
Por tanto, si podemos determinar que
dónde
entonces podemos determinar si los dos polinomios son equivalentes.
La comparación de polinomios tiene aplicaciones para programas de ramificación (también llamados diagramas de decisión binarios ). Un programa de ramificación de una sola lectura se puede representar mediante un polinomio multilineal que calcula (sobre cualquier campo) en {0,1} -introduce la misma función booleana que el programa de ramificación, y dos programas de ramificación calculan la misma función si y solo si el los polinomios correspondientes son iguales. Por lo tanto, la identidad de las funciones booleanas calculadas por programas de ramificación de una sola lectura se puede reducir a pruebas de identidad polinomial.
La comparación de dos polinomios (y por lo tanto probar las identidades polinomiales) también tiene aplicaciones en la compresión 2D, donde el problema de encontrar la igualdad de dos textos 2D A y B se reduce al problema de comparar la igualdad de dos polinomios. y .
Prueba de primordialidad
Dado , es un numero primo ?
Un algoritmo aleatorio simple desarrollado por Manindra Agrawal y Somenath Biswas puede determinar probabilísticamente si es primo y utiliza pruebas de identidad polinomial para hacerlo.
Proponen que todos los números primos n (y solo los números primos) satisfacen la siguiente identidad polinomial:
Esta es una consecuencia del endomorfismo de Frobenius .
Dejar
Luego iff n es primo . La prueba se puede encontrar en [4]. Sin embargo, dado que este polinomio tiene grado, y desde puede o no ser un primo, el método Schwartz-Zippel no funcionaría. Agrawal y Biswas utilizan una técnica más sofisticada, que divide por un polinomio mónico aleatorio de pequeño grado.
Los números primos se utilizan en varias aplicaciones, como el tamaño de la tabla hash, los generadores de números pseudoaleatorios y en la generación de claves para criptografía . Por lo tanto, encontrar números primos muy grandes (del orden de (al menos)) se vuelve muy importante y se requieren algoritmos de prueba de primalidad eficientes.
Combinación perfecta
Dejar ser una gráfica de n vértices donde n es par. ¿ G contiene una combinación perfecta ?
Teorema 2 ( Tutte 1947 ): Un determinante de la matriz de Tutte no es un polinomio 0 si y solo si existe una coincidencia perfecta.
Un subconjunto D de E se llama un juego si cada vértice en V es incidente con a lo sumo un borde en D . Un juego es perfecto si cada vértice en V tiene exactamente un borde que es incidente a que en D . Cree una matriz A de Tutte de la siguiente manera:
dónde
El determinante de la matriz de Tutte (en las variables x ij ,) se define entonces como el determinante de esta matriz de simetría asimétrica que coincide con el cuadrado del pfaffian de la matriz A y no es cero (como polinomio) si y solo si existe una coincidencia perfecta. Luego, se puede usar la prueba de identidad polinomial para encontrar si G contiene una coincidencia perfecta. Existe un algoritmo determinista de caja negra para gráficos con permanentes delimitados polinomialmente (Grigoriev y Karpinski 1987). [5]
En el caso especial de un gráfico bipartito equilibrado envértices esta matriz toma la forma de una matriz de bloques
si las primeras m filas (respectivamente columnas) están indexadas con el primer subconjunto de la bipartición y las últimas m filas con el subconjunto complementario. En este caso el pfaffian coincide con el determinante habitual de la matriz X m × m (hasta el signo). Aquí X es la matriz de Edmonds .
Determinante de una matriz con entradas polinomiales
Dejar
ser el determinante de la matriz polinomial .
Actualmente, no se conoce ningún algoritmo de tiempo sub-exponencial que pueda resolver este problema de manera determinista. Sin embargo, existen algoritmos polinomiales aleatorios cuyo análisis requiere un límite en la probabilidad de que un polinomio distinto de cero tenga raíces en puntos de prueba seleccionados al azar.
Notas
- ↑ ( Schwartz 1980 )
- ↑ ( Zippel, 1979 )
- ^ ( DeMillo y Lipton 1978 )
- ^ Ö. Ore, Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. Yo (1922), no. 7, 15 páginas.
- ↑ ( Grigoriev y Karpinski, 1987 )
Referencias
- Agrawal, Manindra; Biswas, Somenath (21 de febrero de 2003). "Pruebas de identidad y primordialidad a través del resto chino" . Revista de la ACM . 50 (4): 429–443. doi : 10.1145 / 792538.792540 . S2CID 13145079 . Consultado el 15 de junio de 2008 .
- Berman, Piotr; Karpinski, Marek ; Larmore, Lawrence L .; Plandowski, Wojciech; Rytter, Wojciech (2002). "Sobre la complejidad de la coincidencia de patrones para textos bidimensionales altamente comprimidos" (ps) . Revista de Ciencias de la Computación y Sistemas . 65 (2): 332–350. doi : 10.1006 / jcss.2002.1852 . Consultado el 15 de junio de 2008 .
- Grigoriev, Dima; Karpinski, Marek (1987). El problema de concordancia para gráficas bipartitas con permanentes acotadas polinomialmente está en NC . Actas del Simposio anual sobre fundamentos de la informática . págs. 166-172. doi : 10.1109 / SFCS.1987.56 . ISBN 978-0-8186-0807-0. S2CID 14476361 .
- Moshkovitz, Dana (2010). Una prueba alternativa del lema de Schwartz-Zippel. ECCC TR10-096
- DeMillo, Richard A .; Lipton, Richard J. (1978). "Un comentario probabilístico sobre la prueba del programa algebraico". Cartas de procesamiento de información . 7 (4): 193-195. doi : 10.1016 / 0020-0190 (78) 90067-4 .
- Rudich, Steven (2004). AMS (ed.). Teoría de la complejidad computacional . Serie de matemáticas IAS / Park City. 10 . ISBN 978-0-8218-2872-4.
- Schwartz, Jack (octubre de 1980). "Algoritmos probabilísticos rápidos para la verificación de identidades polinomiales" (PDF) . Revista de la ACM . 27 (4): 701–717. CiteSeerX 10.1.1.391.1254 . doi : 10.1145 / 322217.322225 . S2CID 8314102 . Consultado el 15 de junio de 2008 .
- Tutte, WT (abril de 1947). "La factorización de gráficos lineales". J. London Math. Soc . 22 (2): 107-111. doi : 10.1112 / jlms / s1-22.2.107 . hdl : 10338.dmlcz / 128215 .
- Zippel, Richard (1979). "Algoritmos probabilísticos para polinomios dispersos". Computación simbólica y algebraica . Apuntes de conferencias en informática . 72 . págs. 216–226. doi : 10.1007 / 3-540-09519-5_73 . ISBN 978-3-540-09519-4.
- Zippel, Richard (febrero de 1989). "Una separación explícita del tiempo polinomial aleatorio relativizado y el tiempo polinomial determinista relativizado" (ps) . Consultado el 15 de junio de 2008 .
- Zippel, Richard (1993). Springer (ed.). Cálculo polinomial eficaz . Springer International Series en Ingeniería y Ciencias de la Computación. 241 . ISBN 978-0-7923-9375-7.
enlaces externos
- La curiosa historia del lema de Schwartz-Zippel , por Richard J. Lipton