¿Clase de complejidad de este problema?

Estoy tratando de entender a qué clase de complejidad pertenece el siguiente problema:

Problema de raíz polinómica exponencial (EPRP)

Sea un polinomio con deg ( p ) ≥ 0 con coeficientes extraídos de un campo finito G F ( q ) con q un número primo y r una raíz primitiva para ese campo. Determine las soluciones de: p ( x ) = r x (o de manera equivalente, los ceros de p ( x ) - r x ) donde r x significa exponiendo r .$p(x)$$\deg(p) \geq 0$$GF(q)$$q$$r$

Tenga en cuenta que, cuando (el polinomio es una constante), este problema vuelve al problema de logaritmo discreto, que se cree que es NP-Intermedio, es decir, está en NP pero no en P ni NP-completo.$\deg(p)=0$

Que yo sepa, no existen algoritmos eficientes (polinómicos) para resolver este problema (los algoritmos de Berlekamp y Cantor-Zassenhaus requieren un tiempo exponencial). Encontrar raíces para tal ecuación se puede hacer de dos maneras:

• Pruebe todos los elementos posibles en el campo y verifique si satisfacen la ecuación o no. Claramente, esto requiere un tiempo exponencial en el tamaño de bits del módulo de campo;$x$

• La exponencial se puede reescribir en forma polinómica, utilizando la interpolación de Lagrange para interpolar los puntos { ( 0 , r 0 ) , ( 1 , r 1 ) , … , ( q - 1 , r q - 1 ) } , determinando un polinomio f ( x ) . Este polinomio es idéntico a r x precisamente porque estamos trabajando en un campo finito. Entonces, la diferencia $r^x$$\{(0,r^0),(1,r^1),\ldots,({q-1},r^{q-1})\}$$f(x)$$r^{x}$ , se puede factorizar para encontrar las raíces de la ecuación dada (usando los algoritmos de Berlekamp o Cantor-Zassenhaus) y las raíces leen los factores. Sin embargo, este enfoque es incluso peor que la búsqueda exhaustiva: dado que, en promedio, un polinomio que pasa por n puntos dados tendrá n coeficientes no nulos, incluso solo la entrada a la interpolación de Lagrange requerirá un espacio exponencial en el tamaño de bit del campo.$p(x) - f(x)$$n$$n$

¿Alguien sabe si se cree que este problema es NP-intermedio también o si pertenece a alguna otra clase de complejidad? Una referencia será muy apreciada. Gracias.

intentará responder esto. no hay referencias dadas en la pregunta pero se le da un acrónimo "EPRP" como si más de una persona la hubiera estudiado. ¿Alguien sabe si ese es el caso? el interrogador MC parece tener un bkg significativo en esta área, pero ayudaría significativamente enumerar algunas referencias "cercanas" conocidas / revisadas para comprender por qué tienen alguna brecha que no cubre (?) este caso supuestamente especial.

Por lo general, ayuda encontrar "referencias disponibles más cercanas" y determinar cómo el problema es diferente o similar. Aquí hay una referencia completa que parece considerar problemas estrechamente relacionados. piense que el interrogador MC debería tratar de localizar el caso más cercano del problema en esta referencia, o tal vez en otro, y luego señalar cómo este caso es específicamente diferente de los casos de problemas generales dados en la referencia. la referencia tiene una larga lista de referencias relacionadas para verificar también si hay problemas cercanos o relacionados. él considera la complejidad del problema y proporciona algoritmos eficientes de tiempo P para varios casos.

SOBRE LA RESOLUCIÓN DE ECUACIONES POLINOMIALES UNIVARIADAS EN CAMPOS FINITOS Y ALGUNOS PROBLEMAS RELACIONADOS Tsz Wo Sze, Doctor en Filosofía, 2007

... presentamos un algoritmo determinista de tiempo polinómico para resolver ecuaciones polinómicas sobre algunas familias de campos finitos. Tenga en cuenta que las ecuaciones polinómicas son construcciones poderosas. Muchos problemas pueden formularse como ecuaciones polinómicas.