Classe de complexidade deste problema?

Estou tentando entender a qual classe de complexidade o seguinte problema pertence:

Problema de raiz polinomial exponencial (EPRP)

Seja um polinômio com deg ( p ) ≥ 0 com coeficientes extraídos de um campo finito G F ( q ) com q um número primo e r uma raiz primitiva para esse campo. Determine as soluções de: p ( x ) = r x (ou equivalente, os zeros de p ( x ) - r x ) em que r x significa exponenciar r .$p(x)$$\deg(p) \geq 0$$GF(q)$$q$$r$

Observe que, quando (o polinômio é uma constante), esse problema reverte para o Problema do Logaritmo Discreto, que se acredita ser NP-Intermediário, ou seja, está em NP, mas não em P nem NP-completo.$\deg(p)=0$

Que eu saiba, não existem algoritmos eficientes (polinomiais) para resolver esse problema (os algoritmos Berlekamp e Cantor – Zassenhaus exigem tempo exponencial). Encontrar raízes para essa equação pode ser feito de duas maneiras:

• Tente todos os itens possíveis no campo e verifique se eles satisfazem a equação ou não. Claramente, isso requer tempo exponencial no tamanho de bits do módulo de campo;$x$

• O exponencial pode ser reescrito na forma polinomial, usando a interpolação Lagrange para interpolar os pontos { ( 0 , r 0 ) , ( 1 , r 1 ) , … , ( q - 1 , r q - 1 ) } , determinando uma polinômio f ( x ) . Esse polinômio é idêntico a r x precisamente porque estamos trabalhando em um campo finito. Então, a diferença $r^x$$\{(0,r^0),(1,r^1),\ldots,({q-1},r^{q-1})\}$$f(x)$$r^{x}$ , pode ser fatorado para encontrar as raízes da equação dada (usando os algoritmos Berlekamp ou Cantor – Zassenhaus) e as raízes leem os fatores. Entretanto, essa abordagem é ainda pior que a pesquisa exaustiva: uma vez que, em média, uma passagem polinomial por n pontos terá n coeficientes nulos, mesmo que apenas a entrada para a interpolação de Lagrange exija espaço exponencial no tamanho do bit do campo.$p(x) - f(x)$$n$$n$

Alguém sabe se esse problema também é intermediário para o NP ou pertence a qualquer outra classe de complexidade? Uma referência será muito apreciada. Obrigado.

vai dar uma facada em responder a isso. não há referências dadas na pergunta, mas é atribuída uma sigla "EPRP" como se mais de uma pessoa a tivesse estudado. alguém sabe se é esse o caso? o questionador MC parece ter um bkg significativo nessa área, mas ajudaria significativamente a listar alguns árbitros "próximos" conhecidos / revisados ​​para entender por que eles têm alguma lacuna que não cobre (?) esse caso supostamente especial.

geralmente ajuda a encontrar "referências disponíveis mais próximas" e determinar como o problema é diferente ou semelhante. aqui está uma referência abrangente que parece considerar problemas estreitamente relacionados. pense que o questionador MC deve tentar localizar o caso mais próximo do problema nesta ref, ou talvez algum outro, e depois apontar como esse caso questionado é especificamente diferente dos casos gerais de problemas dados na ref. o árbitro tem uma longa lista de árbitros relacionados para verificar também problemas próximos / relacionados. ele considera a complexidade do problema e fornece algoritmos de tempo P eficientes para vários casos.

SOBRE SOLUÇÃO DE EQUAÇÕES POLINOMIAIS UNIVARIADAS EM CAMPOS FINITOS E ALGUNS PROBLEMAS RELACIONADOS Tsz Wo Sze, Doutor em Filosofia, 2007

... apresentamos um algoritmo determinístico de tempo polinomial para resolver equações polinomiais sobre algumas famílias de campos finitos. Observe que as equações polinomiais são construções poderosas. Muitos problemas podem ser formulados como equações polinomiais.