Let $a,b,c\in\mathbb{Z}$. Assume that $a,c\leq 2^p$ and $b\leq 2^q$ - that is, the bit sizes of $a$ and $c$ are bounded by $p+1$ and the bit size of $b$ is bounded by $q+1$. Can I decide whether $$ a^b=c $$ in poly$(p,q)$-time? Can I decide $a^b=c$ in poly$(p,\log q)$-time?
It is clear that I am not allowed to compute $a^b$ as the size of $a^b$ is exponential in $q$. On the other hand, my intuition says it must be correct: If $q$ is small (compared to $p$), then I can compute $a^b$. Otherwise, it is big, and either $a$ has big bit size so $a^b$ cannot be equal to $c$, or it is small so the bit size of $a^b$ does not actually exceed $p$. I think this argument can be made rigorous. On the other hand, I have no idea if I can actually solve the problem in poly$(p,\log q)$-time. I guess it is not actually correct.
I think this problem can be solved in $O(p^3)$ steps.
First, I assume $a,b,c \ge 0$ (the other cases either reduce to this, or for $b < 0$ have only very simple solutions).
$a=0, a=1$ are again simple to solve, as are $b=0, b=1$.
Now calculate $a^2=a\times a, a^3=a^2\times a,\ldots$ by simply multiplying the previous power by $a$ again, until you either reach $a^b$, or your calculation leads to a number $>2^p$.
If you reach $a^b$, compare it with $c$ and decide. If your calculation reaches a number $>2^p$, then obviously $a^b > c$.
Each multiplication is using 2 numbers $\le 2^p$, so at most $p+1$ binary digits, resulting in $O((p+1)^2)=O(p^2)$ time effort for a multiplication. Since $a\ge 2$, we have that $a^{p+1} \ge 2^{p+1} > 2^p$, so the algorithm ends at the latest after you calculated $a^2,\ldots, a^{p+1}$, which are at most $p$ multiplications.
That means you have at most $p$ multiplications each taking $O(p^2)$ time, giving you $O(p^3)$ time. The comparison (if necessary) takes $O(p)$ time, so is not relevant.
In effect you were right that a big $b$ leads to an "early exit" because the power becomes so big. As can be seen above, $b>p$ is already too big, so the algorithm doesn't need to take $q$ into account at all, at least when just looking if a polynomial time algorithm exists.