I am trying to understand to which complexity class the following problem belongs:
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients drawn from a finite field $GF(q)$ with $q$ a prime number, and $r$ a primitive root for that field. Determine the solutions of: $$p(x) = r^x $$ (or equivalently, the zeros of $p(x) - r^x$) where $r^x$ means exponentiating $r$.
Note that, when $\deg(p)=0$ (the polynomial is a constant), this problem reverts to the Discrete Logarithm Problem, which is believed to be NP-Intermediate, i.e. it is in NP but neither in P nor NP-complete.
To the best of my knowledge, efficient (polynomial) algorithms to solve this problem do not exist (Berlekamp and Cantor–Zassenhaus algorithms require exponential time). Finding roots to such equation can be done in two ways:
Try all possible items $x$ in the field, and check whether they satisfy the equation or not. Clearly, this requires exponential time in the bitsize of the field modulus;
The exponential $r^x$ can be rewritten in polynomial form, by using Lagrange interpolation to interpolate the points $\{(0,r^0),(1,r^1),\ldots,({q-1},r^{q-1})\}$, determining a polynomial $f(x)$. This polynomial is identical to $r^{x}$ precisely because we are working on a finite field. Then, the difference $p(x) - f(x)$, can be factored in order to find the roots of the given equation (using Berlekamp or Cantor–Zassenhaus algorithms) and the roots read off the factors. However, this approach is even worse than exhaustive search: since, on average, a polynomial passing by $n$ given points will have $n$ non-null coefficients, even only the input to Lagrange interpolation will require exponential space in the field bit size.
Does anyone know if this problem is believed to be NP-intermediate as well or belonging to any other complexity class ? A reference will be greatly appreciated. Thanks.
