¿No es trivial la prueba de identidad polinómica sobre expresiones aritméticas * *?

Pruebas de identidad polinomio es el ejemplo típico de un problema conocido para estar en co-RP , pero no se sabe que en P . Sobre los circuitos aritméticos , de hecho parece difícil, ya que el grado del polinomio puede hacerse exponencialmente grande mediante la cuadratura repetida. Esta pregunta aborda la cuestión de cómo solucionar esto y mantener el problema en tiempo polinómico aleatorio.

Por otro lado, cuando el problema se presenta inicialmente (por ejemplo, aquí ), a menudo se ilustra sobre expresiones aritméticas que contienen solo constantes, variables, suma y multiplicación. Tales polinomios tienen un grado total en la mayoría de los polinomios en la longitud de la expresión de entrada, y para cualquier polinomio de este tipo, el tamaño del valor de salida es polinomial en el tamaño de los valores de entrada. Pero dado que un polinomio de grado tiene como máximo raíces, ¿no es esto trivial? Simplemente evalúe el polinomio sobre los racionales en cualquier$d$$d$ $d + 1$puntos distintos y compruebe si el resultado es cero en cada punto. Esto debería llevar solo tiempo polinomial. ¿Es esto correcto? Si es así, ¿por qué las expresiones aritméticas sin subexpresiones compartidas se usan a menudo como ejemplos, cuando compartir es esencial para la dificultad del problema?

Eso no se sabe que sea trivial .

El polinomio tiene un número infinito de raíces. (Cuando cualquiera de las variables es cero, la otra variable no afectará el valor del polinomio).$x \cdot y$

Para un polinomio univariado , sí, es así de fácil.$p(x)$

Para un polinomio multivariado , no, este algoritmo no funciona.$p(x_1,x_2,\dots,x_k)$

En particular, cuando escribe "un polinomio de grado tiene como máximo raíces", eso es cierto para los polinomios univariados , pero no es cierto en general para los polinomios multivariados. Ricky Demer da un ejemplo simple: es de grado dos, pero tiene infinitas raíces.$d$$d$$p(x)$$p(x,y) = xy$

Aquí hay una forma más general / abstracta de comprender el significado / dureza de las pruebas de identidad polinomial en CS. Una de las razones por las que las pruebas de identidad polinomiales se están estudiando intensamente en este momento porque se sabe que está estrechamente vinculada a la complejidad del circuito booleano. imagine tomar dos circuitos booleanos arbitrarios y luego convertirlos (es decir, configurar básicamente un mapeo 1-1) en polinomios multivariados. Esto no es tan difícil. básicamente uno usa valores de 0/1 para representar falso / verdadero y las construcciones están configuradas en documentos antiguos. entonces las raíces del polinomio corresponden a asignaciones variables T / F que satisfacen las fórmulas / circuitos.

después de esta configuración, PIT es básicamente el mismo problema que determinar si dos circuitos binarios son equivalentes. también hay otras pruebas más profundas (más recientes) que dicen que es casi equivalente en complejidad a factorizar polinomios. [ 1 ] por lo que uno termina con un resultado como el siguiente: si uno puede resolver PIT "rápidamente" significa que dos grandes circuitos pueden ser en comparación con la equivalencia "rápidamente", lo cual es poco probable. Entonces, una forma aproximada de entender el problema es que es casi equivalente a problemas no triviales en la teoría de circuitos booleanos.