Sobre la desaleatorización de la prueba de identidad polinómica

En la prueba de identidad polinómica buscamos un algoritmo determinista para inferir la igualdad de dos polinomios . Desrandomizar algoritmos aleatorizados eficientes conocidos y producir un algoritmo determinista eficiente es un importante problema abierto. ¿Existe un problema completo para PIT de modo que la desrandomización de las pruebas de identidad para esta clase de polinomios resuelva este problema abierto? Si no, ¿hay clases de polinomios donde se resuelve este problema y clases donde están abiertos?$g,h\in\Bbb Z[x_1,\dots,x_n]$

[tl;dr] ¡Se sabe mucho y es un área muy activa! [/tl;dr]

Es importante especificar la representación de los polinomios de entrada, ya que si se dan como listas de coeficientes o monomios distintos de cero, el problema es trivial. Por lo tanto, generalmente se supone que los polinomios se dan como circuitos aritméticos (también conocidos como programas de línea recta). Y el caso general en realidad se reduce a probar si un polinomio dado es el polinomio cero.

Se han estudiado dos configuraciones principales: el caso de la caja blanca en el que uno tiene el circuito aritmético y puede inspeccionarlo, y el caso de la caja negra en el que uno sabe algunas cosas sobre el circuito (tamaño, grado formal, ...) pero no puede inspeccionarlo, solo evaluarlo en algunos valores.

Estas son algunas de las restricciones en los circuitos que se han estudiado:

• $2$$3$$4$$3$$4$
• Fan-in superior / inferior: para circuitos de profundidad limitada, se han demostrado muchos resultados cuando el fan-in (o arity, que es el número de entradas a una puerta determinada) de la puerta superior o de las puertas inferiores está limitado.
• También se han estudiado otras restricciones, como un límite en la cantidad de veces que se usa una variable.

Esta encuesta realizada por Nitin Saxena es una buena fuente para estos resultados. Sin embargo, tenga en cuenta que ya tiene más de un año (!), Y esta es un área muy activa. Por lo tanto, los resultados más recientes no están cubiertos.

Finalmente, hay vínculos entre la desleatización de PIT y la desleatización de otros problemas:

• Lema de normalización de Noether , de Ketan D. Mulmuley;
• Factorización polinómica multivariante , por Swastik Kopparty, Shubhangi Saraf y Amir Shpilka.