Complexity class of this problem? 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.
will take a stab at answering this. there are no refs given in the question but it is given an acronym "EPRP" as if more than one person has studied it. does anyone know if that is the case? the questioner MC seems to have significant bkg in this area but it would help significantly to list some "nearby" refs known/reviewed to understand why they have some gap that doesnt (?) cover this supposedly special case.

it usually helps to find "nearest available refs" and determine how the problem is different or similar. here is a comprehensive ref that seems to consider closely related problem(s). think that the questioner MC should try to locate the nearest case of the problem in this ref, or maybe some other one, and then point out how this case asked about is specifically different than general problem cases given in the ref. the ref has a long list of related refs to also check for nearby/related problem(s). he considers the complexity of the problem and gives efficient P-time algorithms for various cases.

ON SOLVING UNIVARIATE POLYNOMIAL
EQUATIONS OVER FINITE FIELDS
AND SOME RELATED PROBLEMS
Tsz Wo Sze, Doctor of Philosophy, 2007


  ...we present a deterministic polynomial-time algorithm to
  solve polynomial equations over some families of finite fields. Note that polynomial
  equations are powerful constructs. Many problems can be formulated as polynomial
  equations.