En matemáticas, la prueba de identidad polinomial (PIT) es el problema de determinar de manera eficiente si dos polinomios multivariados son idénticos. Más formalmente, un algoritmo PIT recibe un circuito aritmético que calcula un polinomio p en un campo y decide si p es el polinomio cero. La determinación de la complejidad computacional requerida para las pruebas de identidad polinomial es uno de los problemas abiertos más importantes en la complejidad de la computación algebraica.
Descripción
La pregunta "¿ igual "es una pregunta sobre si dos polinomios son idénticos. Como con cualquier pregunta de prueba de identidad polinomial, se puede transformar trivialmente en la pregunta" ¿Un determinado polinomio es igual a 0? "; en este caso, podemos preguntar" ¿ "? Si se nos da el polinomio como una expresión algebraica (en lugar de una caja negra), podemos confirmar que la igualdad se mantiene a través de la multiplicación y la suma de fuerza bruta, pero la complejidad temporal del enfoque de fuerza bruta crece a medida que, dónde es el número de variables (aquí, : es el primero y es el segundo), y es el grado del polinomio (aquí,). Si y son ambos grandes, crece exponencialmente. [1]
PIT se refiere a si un polinomio es idéntico al polinomio cero, en lugar de si la función implementada por el polinomio siempre se evalúa como cero en el dominio dado. Por ejemplo, el campo con dos elementos, GF (2) , contiene solo los elementos 0 y 1. En GF (2),siempre evalúa a cero; a pesar de esto, PIT no considerapara ser igual al polinomio cero. [2]
La determinación de la complejidad computacional requerida para las pruebas de identidad polinomial es uno de los problemas abiertos más importantes en el subcampo matemático conocido como "complejidad de computación algebraica". [1] [3] El estudio de PIT es un componente básico de muchas otras áreas de complejidad computacional, como la prueba de que IP = PSPACE . [1] [4] Además, PIT tiene aplicaciones para matrices de Tutte y también para pruebas de primalidad , donde las técnicas PIT llevaron a la prueba de primalidad AKS , el primer algoritmo de tiempo polinómico determinista (aunque poco práctico) para pruebas de primalidad. [1]
Enunciado formal del problema
Dado un circuito aritmético que calcula un polinomio en un campo , determine si el polinomio es igual al polinomio cero (es decir, el polinomio sin términos distintos de cero). [1]
Soluciones
En algunos casos, la especificación del circuito aritmético no se le da al solucionador PIT, y el solucionador PIT solo puede ingresar valores en una "caja negra" que implementa el circuito y luego analizar la salida. Tenga en cuenta que las soluciones siguientes asumen que cualquier operación (como una multiplicación) en el campo dado toma un tiempo constante; Además, todos los algoritmos de caja negra a continuación asumen que el tamaño del campo es mayor que el grado del polinomio.
El algoritmo de Schwartz-Zippel proporciona una solución probabilística práctica, simplemente probando las entradas de forma aleatoria y verificando si la salida es cero. Fue el primer algoritmo PIT de tiempo polinomial aleatorio que demostró ser correcto. [1] Cuanto mayor sea el dominio del que se extraen las entradas, es menos probable que Schwartz-Zippel falle. Si los bits aleatorios son escasos, el algoritmo Chen-Kao (sobre los racionales) o el algoritmo Lewin-Vadhan (sobre cualquier campo) requieren menos bits aleatorios a costa de más tiempo de ejecución requerido. [2]
Un PIT escaso tiene como máximotérminos monomiales distintos de cero . Un PIT disperso se puede resolver determinísticamente en tiempo polinomial del tamaño del circuito y el númerode monomios, [1] ver también. [5]
Un PIT de bajo grado tiene un límite superior en el grado del polinomio. Cualquier problema de PIT de bajo grado puede reducirse en tiempo subexponencial del tamaño del circuito a un problema de PIT para circuitos de profundidad cuatro; por lo tanto, se estudia intensamente el PIT para circuitos de profundidad cuatro (y menos). [1]
Ver también
enlaces externos
- Notas de la conferencia sobre "Pruebas de identidad polinomial por el lema de Schwartz-Zippel"
- Pruebas de identidad polinomial por Michael Forbes - MIT en YouTube
- Ganador del premio por pruebas de identidad polinomial
Referencias
- ^ a b c d e f g h Saxena, Nitin. "Progreso en las pruebas de identidad polinomial". Boletín de la EATCS 99 (2009): 49-79.
- ^ a b Shpilka, Amir y Amir Yehudayoff. "Circuitos aritméticos: una encuesta de resultados recientes y preguntas abiertas". Fundamentos y tendencias en informática teórica 5.3–4 (2010): 207-388.
- ^ Dvir, Zeev y Amir Shpilka. "Códigos decodificables localmente con dos consultas y pruebas de identidad polinomial para circuitos de profundidad 3". Revista SIAM de Computación 36.5 (2007): 1404-1434.
- ^ Adi Shamir . "IP = PSPACE". Revista de la ACM (JACM) 39.4 (1992): 869-877.
- ^ Grigoriev, Dima, Karpinski, Marek y Singer, Michael F., "Algoritmos paralelos rápidos para interpolación polinomial multivariante dispersa sobre campos finitos", SIAM J. Comput., Vol 19, No.6, págs. 1059-1063, diciembre 1990