How difficult is finding $i$ in tetration $^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\cdot^{g}}}}_i\equiv v \mod P$ for $v\in[1,P-1]$

For a given $g\in\mathbb N$ there will be at most $O(\log P)$ distinct titrations modulo $P$. Thus there are only a small number of examples where $|\{{}^jg\mod P\}|=P-1$. In other cases, if the tetration modulo $P$ can be effectively computed, then the problem is easy to solve by exhaustion.

To understand the small size of $|\{{}^jg\mod P\}|$, note that for if $P$ does not divide $g$ then for $i\ge 1$ by Euler's theorem $${}^ig\equiv g^{{}^{i-1}g}\equiv g^{{}^{i-1}g\mod{\phi(P)}}\pmod P.$$ We now note that ${}^{i-1}g\mod{\phi(P)}$ takes on at most $\phi(\phi(P))$ different values and the these cycle with period at most $\phi(\phi(P))$. It follows that for $i\ge 1$, ${}^ig\mod P$ takes on a most $\phi(\phi(P))$ values. Iterating the argument write $\phi_k(x)$ for the $k$-iterated totient function $\phi_1(x)=\phi(x)$, $\phi_k(x)=\phi(\phi_{k-1}(x))$. We then see that for $i\ge k$, ${}^{i-k}g\mod{\phi_k(P)}$ takes on at most $\phi_{k+1}(P)$ different values and hence for $i\ge k$, ${}^ig\mod P$ takes on a most $\phi_{k+1}(P)$ values. Theres some elision of here about details when $g$ has a factor in common with $\phi_k(P)$.

Now, we note that for all $n>2$ we have $2|\phi(n)$ and that for all $m$ we have $\phi(2m)\le m/2$. It follows that $\phi_k(P)\le P/2^{k-1}$. Also because $\phi_k(P)$ is an integer, for $k>\lceil\log_2P\rceil+1$ we have $\phi_k(P)=1$. Thus if we write $L=\lceil\log_2P\rceil+1$ we have for $i,j>L$ ${}^ig\equiv{}^jg\pmod P$.

Computing the tetrations can be done by square-and-multiply methods provided that one can compute all of the $\phi_k(P)$.